Cerința

Se dă un graf orientat ponderat cu n noduri și m arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime, a[i][j] fiind costul minim al unui drum de la i la j, dacă există un asemenea drum, sau -1 în caz contrar.

Date de intrare

Fișierul de intrare roy-floyd.in conține pe prima linie numerele n m, iar următoarele linii câte un triplet i j c, cu semnificația: există arcul (i j) și are costul c.

Date de ieșire

Fișierul de ieșire roy-floyd.out va conține matricea construită, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unui arc va fi mai mic decât 1000
• costul unui drum este egal cu suma costurilor arcelor care îl compun

Exemplu:

roy-floyd.in

5 6
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

roy-floyd.out

0 -1 1 -1 -1 
2 0 3 -1 -1 
-1 -1 0 -1 -1 
3 1 4 0 -1 
5 3 5 2 0