== include(page="template/taskheader" task_id="viteza2") ==

Vitezomanul Mirel tocmai si-a cumparat o masina IA-3.0 si vrea sa se plimbe cu ea prin Targu Mures in noua sa masina IA-X3. **[cezar: dafuq did i just read? carception?]** 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 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 cat poate sa prinda mai multa viteza 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.

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$ orase respectand cerintele lui.

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

h2. Date de intrare