== include(page="template/taskheader" task_id="regat") ==
Regele Gefghev se confruntă cu o nouă problemă de interes naţional. Regatul condus de el conţine $N$ oraşe, numerotate de la $1$ la $N$, legate între ele prin $N–1$ poteci bidirecţionale. Fiecare potecă are o anumită lungime exprimată în metri. Între oricare două oraşe există cel mult o singură potecă şi se poate ajunge din orice oraş în oricare alt oraş, mergând numai pe potecile existente. Regelui îi place să călătorească, de aceea el îşi ia concediu $M$ zile şi plănuieşte să organizeze $M$ călătorii. La începutul fiecărei zile Gefghev alege un oraş de pornire $x$ şi vrea să parcurgă începând cu acel oraş un drum de lungime maximă. Drumul parcurs de rege este de fapt o succesiune de oraşe distincte ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) astfel încât există o potecă între oricare două oraşe $a{~i~}$ şi $a{~i+1~}$ $(i < k)$ iar $a{~1~}$ $= x$. Lungimea drumului este dată de suma lungimilor potecilor care-l compun. Fiindcă nu vrea să se plictisească, regele Gefghev vrea să parcurgă în fiecare zi un drum diferit. Două drumuri $d{~1~}$ = ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) şi $d{~2~}$ = ( $b{~1~}$ , $b{~2~}$ , $b{~3~}$ ... $b{~p-1~}$ , $b{~p~}$ ) sunt diferite dacă:
Regele Gefghev se confruntă cu o nouă problemă de interes naţional. Regatul condus de el conţine $N$ oraşe, numerotate de la $1$ la $N$, legate între ele prin $N–1$ poteci bidirecţionale. Fiecare potecă are o anumită lungime exprimată în metri. Între oricare două oraşe există cel mult o singură potecă şi se poate ajunge din orice oraş în oricare alt oraş, mergând numai pe potecile existente. Regelui îi place să călătorească, de aceea el îşi ia
concediu $M$ zile şi plănuieşte să organizeze $M$ călătorii. La începutul fiecărei zile Gefghev alege un oraş de pornire $x$ şi vrea să parcurgă începând cu acel oraş un drum de lungime maximă. Drumul parcurs de rege este
de fapt o succesiune de oraşe distincte ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) astfel încât există o potecă între oricare două oraşe $a{~i~}$ şi $a{~i+1~}$ $(i < k)$ iar $a{~1~}$ $= x$. Lungimea drumului este dată de suma lungimilor potecilor care-l compun. Fiindcă nu vrea să se plictisească, regele Gefghev vrea să parcurgă în fiecare zi un drum diferit. Două
drumuri $d{~1~}$ = ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) şi $d{~2~}$ = ( $b{~1~}$ , $b{~2~}$ , $b{~3~}$ ... $b{~p-1~}$ , $b{~p~}$ ) sunt diferite dacă:
* $k ≠ p$ sau
* $k = p$ şi există măcar o poziţie $q$ astfel încât $a{~q~} ≠ b{~q~}$
Scrieţi un program care determină pentru regele Gefghev lungimea drumului parcurs în fiecare din cele $M$ călătorii.
h2. Date de intrare
Date de intrare
Pe prima linie a fişierului de intrare $regat.in$ se află două numere întregi $N$ şi $M$ separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele $N-1$ linii se află câte trei numere $a$, $b$ şi $c$ separate prin câte un singur spaţiu, având semnificaţia că există un drum de la oraşul $a$ la oraşul $b$, iar acest drum are lungimea de $c$ metri. Pe următoarele $M$ linii se află câte un număr cuprins între $1$ şi $N$, pe linia $N+1+i$ aflându-se oraşul din care regele îşi începe a $i$-a călătorie.
h2. Date de ieşire
Date de ieşire
În fişierul de ieşire regat.out se vor afla $M$ numere naturale, pe linia $i$ se va afla lungimea drumului parcurs de rege in călătoria din ziua $i$.
