Viteza2

viteza2

== 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. 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.
 
Stiind $N$, $M$ si cele $M$ strazi aflati pentru Mirel drumul cel mai scurt dintre $oricare 2$ orase respectand cerintele lui.

Poveste şi cerinţă...

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.

Fişierul de intrare $viteza2.in$ ...

h2. Date de iesire

h2. Date de ieşire

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

În fişierul de ieşire $viteza2.out$ ...

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. viteza2.in |_. viteza2.out |

| 4 4
1 4 1
1 2 3
2 3 7
3 4 8
| 0 3 9 1
3 0 7 15
-1 7 0 8
1 4 8 0

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Observatii

h3. Explicaţie

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

...

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

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