== include(page="template/taskheader" task_id="dbz") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $dbz.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $dbz.out$ ...
Î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ă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 500$
* $1 ≤ M ≤ 30 000$
* $1 ≤ durata fiecărei deplasări z ≤ 9 000 (nu este over 9000!)$
* $Pentru fiecare pereche de planete (x, y) există maxim un drum direct între ele.$
h2. Exemplu
table(example). |_. dbz.in |_. dbz.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
| 9 9 9 9 13
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="dbz") ==
