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

Poveste şi cerinţă...

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

Fişierul de intrare $regat.in$ ...

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

În fişierul de ieşire $regat.out$ ...

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$.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 100.000$
* Lungimile drumurilor sunt numere naturale cuprinse în intervalul $[1, 10.000]$
* Regele poate începe mai multe călătorii din acelaşi oraş
* Regele va avea întotdeauna posibilitatea de a efectua toate călătoriile
* Pentru $20%$ din teste $N ≤ 700$
* Pentru $40%$ din teste fiecare călătorie începe dintr-un oraş diferit

h2. Exemplu
table(example). |_. regat.in |_. regat.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 8 5
1 2 3
2 3 5
3 4 14
2 6 3
2 7 9
7 8 10
5 6 20
1
2
1
4
3
| 26
23
22
42
28

|
h3. Explicaţie

...

Prima călătorie începe în oraşul $1$ şi se finalizează în orasul $5$. Lungimea drumului este $26$. Nu există alt oraş la o distanţă strict mai mare decât $26$. A doua oară cand regele începe o calatorie din orasul $1$, o poate încheia în oricare din oraşele $4$ sau $8$, lungimea drumului fiind $22$.
 

== include(page="template/taskfooter" task_id="regat") ==