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 orase $(i, j)$ cat de repede poate sa ajunga din orasul $i$ la orasul $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$ orase respectand cerintele lui.

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

h2. 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.

Urmatoarele $M$ linii contin fiecare cate $3$ numere $A$, $B$, si $D$ cu semnificatia ca intre intersectiile $A$ si $B$ exista o strada de lungime $D$ care le uneste.

h2. Date de iesire