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

!>problema/dbz?img.png!
 

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