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 (a1, a2, a3 ... ak-1, ak) astfel încât există o potecă între oricare două oraşe ai şi ai+1 (i < k) iar a1 = 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 d1 = (a1, a2, a3 ... ak-1, ak) şi d2 =( b1, b2, b3 ... bp-1, bp) sunt diferite dacă:
• k ≠ p sau
• k = p şi există măcar o poziţie q astfel încât aq ≠ bq.

Cerinţă

Scrieţi un program care determină pentru regele Gefghev lungimea drumului parcurs în fiecare dintre 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 în călătoria din ziua i.

Restricţii

• 1 ≤ N, M ≤ 100000
• Lungimile drumurilor sunt numere naturale cuprinse în intervalul [1, 10000]
• 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

Exemple

regat.in	regat.out	Explicaţii
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	Prima călătorie începe în oraşul 1 şi se finalizează în orasul 4. Lungimea drumului este 26. Nu există alt oraş la o distanţă strict mai mare decât 26. A doua oară când regele începe o călătorie din oraşul 1, o poate încheia în oricare dintre oraşele 4 sau 8, lungimea drumului fiind 22.

autor: Stud. Adrian Airinei

propunător: Prof. Emanuela Cerchez

Liceul de Informatică ″Grigore Moisil″

emanuela.cerchez@gmail.com