== include(page="template/taskheader" task_id="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.

Vitezomanul Mirel tocmai si-a cumparat o masina IA-3.0 si vrea sa se plimbe cu ea prin Targu Mures. Orasul este format din $M$ strazi bidirectionale si $N$ intersectii, fiecare strada unind $2$ intersectii distincte. Avand mult timp la dispozitie el vrea pentru fiecare pereche de orase $(i, j)$ sa ajunga cat mai repede in orasul $j$ plecand din orasul $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.

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$ intersectii 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