Fişierul intrare/ieşire:	viteza2.in, viteza2.out	Sursă	Algoritmiada 2012, Runda finala
Autor	Cosmin Gheorghe	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.4 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Viteza2

Vitezomanul Mirel tocmai si-a cumparat un nou IA-mobil(o masina de ultima generatie) si vrea sa se plimbe cu el prin Targu Mures. Orasul este format din M strazi bidirectionale si N intersectii, fiecare strada unind 2 intersectii distince. Avand mult timp la dispozitie el vrea pentru fiecare pereche de intersectii (i, j) sa ajunga cat mai repede in intersectia j plecand din interectia i si mergand doar pe strazile din oras. Din pacate pentru el (si pentru voi) vrea neaparat ca pe orice strada pe care merge sa prinda o viteza mai mare decat a prins pe strada anterioara.
In fiecare intersectie el trebuie sa franeze pentru a schimba strada, iar cu cat strada este mai lunga cu atat poate sa ajunga la o viteza mai mare pe ea.
Din pacate Mirel nu se pricepe la mai mult decat condus asa ca va roaga pe voi sa aflati pentru fiecare pereche de intersectii (i, j) cat de repede poate sa ajunga din intersectia i la intersectia j atingand pe fiecare strada o viteza mai mare decat pe anterioara.

Stiind N, M si cele M strazi aflati pentru Mirel drumul cel mai scurt dintre oricare 2 intersectii respectand cerintele lui.

Date de intrare

Fişierul de intrare viteza2.in contine pe prima linie N si M reprezentand numarul de intersectii si strazi din oras.
Urmatoarele M linii contin fiecare 3 numere A, B, si D cu semnificatia ca intre intersectiile A si B exista o strada de lungime D care le uneste.

Date de iesire

În fişierul de ieşire viteza2.out trebuie sa se gaseasca N linii fiecare cu cate N numere.
Al j-lea numar de pe a i-a linie trebuie sa reprezinta lungimea minima a unui drum care pleaca din intersectia i, se termina in intersectia j si respecta cerintele lui Mirel. Daca nu exista un drum ce respecta aceste cerinte Mirel va roaga sa afisati -1

Restricţii

• 1 ≤ N ≤ 1.000
• 1 ≤ M ≤ 5.000
• 1 ≤ A, B, ≤ N
• 1 ≤ D ≤ 1.000.000
• Pentru oricare doua intersectii A, B exista maxim o strada care le uneste
• Lungimile strazilor sunt diferite doua cate doua
• Pentru 20% din teste 1 ≤ N ≤ 15 si 1 ≤ M ≤ 50
• Pentru inca 20% din teste 1 ≤ N ≤ 100 si 1 ≤ M ≤ 1000

Exemplu

Observatii

De la intersectia 2 la intersectia 4 exista un drum de lungime 4(2 -> 1 -> 4) insa nu respecta cerintele lui Mirel(mai exact lungimea muchiei de la 1 -> 4 este mai mica decat cea a muchiei 2 -> 1)

Cum se trimit solutii?