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

Speedy $Mirel$ just bought himself a new IA-mobile(a new generation car) and wants to take it to a ride through $Targu Mures$. The city is formed of $M$ bidirectional streets and $N$ intersections, each street connecting $2$ different intersections. Having lots of free time he wants for each pair of cities $(i, j)$ to find the shortest path to intersection $j$ starting from intersection $i$ and going only through streets in the city. Unfortunately for him(and for you) he insists that on each street through which he passes to reach a higher speed than what he has reached on the previous one.
On every intersection he has to brake(so his speed drops to 0) and the longer the street is the higher the speed he can reach on it.
Unfortunately $Mirel$ isn't good at other things besides driving so he asks for your help in determining for each pair of intersections $(i, j)$ how fast can he go from intersection $i$ to intersection $j$ reaching on each street passed a higher speed than on the previous one.

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.

Knowing $N$, $M$ and the $M$ streets find out for $Mirel$ the shortest path between $each 2$ intersections under his restrictions.

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

h2. Input Data

h2. Date de intrare

The input file $viteza2.in$ contains on the first line 2 numers $N$ and $M$ reprezenting the number of intersections and the number of streets in the city.
The next $M$ lines each contain 3 numbers $A$, $B$ and $D$ which describe a street of distance $D$ in the city connecting intersections $A$ and $B$.

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.

h2. Output Data

h2. Date de iesire

In the output file $viteza2.out$ there should be exactly $N$ lines each containing $N$ numbers.
The $j-th$ number on the $i-th$ line must represent the shortest path from intersection $i$ to intersection $j$ respecting $Mirel$'s restrictions. If there is no such path you must print $-1$ instead.

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

h2. Restrictions

h2. Restricţii

* $1 ≤ N ≤ 1.000$
* $1 ≤ M ≤ 5.000$
* $1 ≤ A, B, ≤ N$
* $1 ≤ D ≤ 1.000.000$

* $For each 2 intersections A and B there is *maximum* one street connecting them$
* $Any 2 street have different lengths$
* $For 20% of the tests 1 ≤ N ≤ 15 si 1 ≤ M ≤ 50$
* $For another 20% of the tests 1 ≤ N ≤ 100 si 1 ≤ M ≤ 1000$

* $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. Example

h2. Exemplu

table(example). |_. viteza2.in |_. viteza2.out |
| 4 4

1 4 8 0
|

h3. Observations

h3. Observatii

From intersection $2$ to intersection $4$ there is also a path of length $4(2 -> 1 -> 4)$ but it does not respect Mirel's restrictions(the length of the street from $1$ to $4$ is smaller than the length of the street from $2$ to $1$)

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") ==