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. 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 care pot fi utilizate pentru a transporta echipamentul necesar acestui 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 acestea). 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 Olympiland. 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 conțin trei întregi pozitivi separați prin spații, reprezentând numerele celor două orașe, ruta și profitul realizat.

Date de ieșire

În fișierul de ieșire profit.out conține trei numere întregi separate prin spații reprezentând numerele celor două orașe cu ajutorul cărora se poate ajunge la profit maxim urmat de valoarea profitului maxim. Dacă există mai multe soluții, se va afișa oricare soluție corectă.

Restricții

• 2 ≤ N ≤ 10⁵
• 0 ≤ M ≤ 10⁵
• 1 ≤ profitul fiecărei rute ≤ 10³

• În 20% dintre teste : N < 100
• În 40% dintre teste : N < 1 000
• În 70% dintre teste există o rută optimă, inclusiv drumul direct dat in lista drumurilor directe

Exemplu

profit.in	profit.out	Explicație
6 1 2 2 3 2 4 5 4 6 4 4 1 4 10 2 5 20 6 3 15 2 1 1.	5 1 31