Dragon Ball Z

Goku a ajuns în viața de apoi, să se antreneze pentru lupta finală cu Majin Boo. El vrea să se antreneze pe cele $N$ planete cu Kai, și știe în cât timp se poate deplasa între anumite perechi de planete (doar între perechile date se poate deplasa). Pentru fiecare planetă pe care ar putea să se afle, vă roagă să îi spuneți care este drumul de durata minimă care ar pleca din acea planetă și care s-ar întoarce tot acolo, folosind un drum care leagă direct două planete maxim o singură dată. El l-a întrebat pe vărul său, Goku Marian, însa acesta nu se prea descurcă și are nevoie de ajutorul vostru.

Date de intrare

Pe prima linie a fișierului de intrare dbz.in se vor afla numerele naturale $N$ și $M$. Pe următoarele $M$ linii vor fi trei numere $x, y$ și $z$, reprezentând faptul că există drum bidirecțional între planetele $x$ şi $y$ cu durată de deplasare $z$.

Date de ieșire

În fișierul de ieșire dbz.out se va afișa, pentru fiecare planetă de la $1$ la $N$, durata minimă a unui drum care pornește de pe acea planetă și se termină tot pe ea, folosind un drum care leagă direct două planete maxim o singură dată. În cazul în care nu există un asemenea drum, afișați numărul $-1$ pentru acea planetă.

Restricții si precizări

• $1 \leq N \leq 1 \ 500$;
• $1 \leq M \leq 30 \ 000$;
• $1 \leq$ durata fiecărei deplasări $z \leq 9 \ 000$ (nu este over $9000!$);
• Pentru fiecare pereche de planete $(x, y)$ există maxim un drum direct între ele.

Exemplu

dbz.in

5 6 
1 2 1 
1 4 2 
4 3 4 
2 3 2 
4 5 3 
3 5 6

dbz.out

9 9 9 9 13