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, \dots 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, \dots a_{k-1}, a_k)$ şi $d_2 = (b_1, b_2, b_3, \dots b_{p-1}, b_p)$ sunt diferite dacă:

• $k \neq p$ sau
• $k = p$ şi există măcar o poziţie $q$ astfel încât $a_q \neq b_q$.

Cerinţă

Scrieţi un program care determină pentru regele Gefghev lungimea drumului parcurs în fiecare din cele $M$ călătorii.

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.

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

Restricții și precizări

• $1 \leq N, M \leq 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 \leq 700$
• Pentru $40\%$ din teste fiecare călătorie începe dintr-un oraş diferit

Exemplu

regat.in

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

regat.out

26
23
22
42
28

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