Fişierul intrare/ieşire:	riremito.in, riremito.out	Sursă	Algoritmiada 2015 Runda Finala
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Riremito

Dragon Quest, un joc clasic de tip RPG va pune la dispozitie un caracter numit Hero cu care sa explorati, sa va bateti cu monstri si sa gasiti comori. De cele mai multe ori comorile sunt ascunse in pesteri si labirinturi care se pot descrie sub forma unor arbori cu costuri pe muchii.Fanii inraiti joaca de nenumarate ori aceste jocuri si dupa o vreme ajung la eficienta maxima, acel moment in care petrec minimul de timp necesar pentru a gasi toate comorile din joc. Ce ii ajuta pe ei pentru a se plimba repede in vizita unui labirint este o vraja foarte puternica numita Riremito. Aceasta vraja il teleporteaza pe jucator instantaneu la intrare, acesta astfel economisind foarte mult timp necesar in plimbarea prin labirinturi.

Producatorii deja obisnuiti cu acesti jucatori incearca din rasputeri sa le prelungeasca timpul de joc acestor fani, pentru ca ei sa nu se plictiseasca prea repede. Deja au primit planul labirinturilor de la designeri si nu mai pot schimba cum arata acestea, insa pot alege intrarea in labirint dintr-un numar restrans de puncte. Ei se intreaba pentru fiecare din aceste puncte posibile de intrare care ar fi costul de vizitare al intregului arbore (jucatorii fiind obligati sa faca asta pentru a descoperi toate comorile).

Date de intrare

Fişierul de intrare riremito.in va contine pe prima linie N numarul de noduri al arborelui ce descrie labirintul.
Urmatoarele N - 1 linii vor descrie muchiile arborelui fiecare pe o linie. Astfel pe fiecare linie se vor gasi 3 numere intregi x, y si z cu semnificatia ca exista o muchie de la nodul cu indice x la nodul cu indice y si care poate fi traversata in z secunde.
Pe urmatorul rand se va afla un numar K care reprezinta numarul de noduri posibile unde ar putea fi amplasat inceputul in labirint, iar pe urmatorul rand se vor afla cele K numere reprezantand indicii nodurile unde ar putea fi amplasat inceputul.

Date de ieşire

În fişierul de ieşire riremito.out trebuie sa se gaseasca K randuri, cate unul pentru fiecare din cele K noduri din fisierul de intrare reprezentand timpul minim de vizitare al intregului arbore cu intrarea fixata in fiecare din cele K noduri.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ x, y ≤ N
• 1 ≤ z ≤ 1.000.000.000
• Riremito este instantaneu si poate fi folosit de oricate ori
• 1 ≤ K ≤ 10
• Pentru 30% din punctaj N ≤ 20

Exemplu

Cum se trimit solutii?