| Fişierul intrare/ieşire: | dbz.in, dbz.out | Sursă | Lot Mehedinți 2015 - Baraj 6 Seniori |
| Autor | Mihai Ciucu | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 2.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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
- 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.
Exemplu
| dbz.in | dbz.out |
|---|---|
| 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 |
