Fișierul intrare/ieșire	profit.in, profit.out	Sursă	Concurs Shumen seniori 2017
Autor	autor necunoscut	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Profit

Sunt N orașe in Olympiland, numerotate de la 1 la N. Unele sunt direct conectate și rețeaua de drumuri este organizată în așa mood încât există un singur drum posibil de la un oraș la altul, care poate să nu fie neapărat direct (trecând prin alte orașe).
Pentru a realiza un mare proiect de infrastructură, a fost creată o lisă a rutelor pentru a transporta echipamentul necesar pentru acest proiect. Un singur transport o sa fie efectuat pe fiecare rută. Un drum este definit de doua orase u si v intre care sunt transportate echipamentele (direcția nu este importantă) și un profit p realizat de către compania care o să facă transportul pe ruta respectivă.

Este organizat un concurs pentru companiile care efectuează transportul. Fiecare companie trebuie să aleagă doua orașe și trebuie să finalizeze transportul echipamentelor pe toate rutele care încep și se termină între cele două orașe inclusiv. Scrieți un program care să aleagă doua orașe din Olympiland pentru a obține profit maxim prin utilizarea rutelor care se află între cele două orașe selectate.

Date de intrare

Fișierul de intrare profit.in conține un număr întreg N reprezentând numărul de orașe din Olymliland. Fiecare din următoarele N – 1 linii, conține două numere întregi pozitive (nu mai mari decât N), separate prin spații, reprezentând o pereche de orașe care sunt direct conectate de către un drum. Următoarea linie conține numărul întreg M reprezentând lungimea listei cu drumurile de transport. Următoarele M linii
Each of the next
M
l
ines contains three space separated positive integers: the numbers of the
two towns, defining the route, and the profit of its realization.

Date de ieșire

În fișierul de ieșire profit.out ...

Restricții

• ... ≤ ... ≤ ...

Exemplu

Explicație

...