Fişierul intrare/ieşire:	mesaj3.in, mesaj3.out	Sursă	Lot Suceava 2007
Autor	Dan-Ionut Fechete	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.35 sec	Limită de memorie	36096 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mesaj 3

Pana nu demult, in Bucovina existau doar N orase conectate intre ele prin N - 1 sosele bidirectionale. Cu toate acestea, se putea ajunge din orice oras in orice alt oras mergand pe una sau mai multe sosele.

Cand Stefan trebuia sa faca un anunt important, el trimitea mesajul catre fiecare dintre cei M mesageri ai sai. Fiecare mesager, dupa primirea mesajului de la Stefan, pleaca sa transmita mesajul primit pe o ruta fixata. Mai exact, mesagerul i (1 ≤ i ≤ M) va transmite mesajul in toate orasele situate pe ruta care porneste din orasul a_i si ajunge in orasul b_i. Pentru a transmite mesajul in toate orasele de pe ruta sa, mesagerul i (1 ≤ i ≤ M) va primi X_i galbeni.

Cerinta

Care este numar minim de galbeni pe care Stefan trebuia sa-l plateasca pentru ca mesajul sau sa ajunga in toate cele N orase din Bucovina?

Date de intrare

Fisierul de intrare mesaj3.in contine pe prima linie numarul natural N, reprezentand numarul de orase din Bucovina. Urmatoarele N - 1 linii contin cate doua numere naturale distincte separate printr-un spatiu a b cu semnificatia "exista o sosea care conecteaza direct orasele a si b". Pe linia N + 1 este scris un numar natural M reprezentand numarul de mesageri. Pe urmatoarele M linii se afla informatii despre cei M mesageri. Pe cea de a i-a linie dintre cele M (1 ≤ i ≤ M) sunt scrise trei numere naturale separate prin cate un spatiu a_i b_i X_i, cu semnificatia "mesagerul i parcurge ruta de la orasul a_i la orasul b_i, fiind platit cu X_i galbeni".

Date de iesire

Fisierul de iesire mesaj3.out va contine o singura linie pe care va fi scris numarul minim de galbeni pe care trebuie sa-i plateasca Stefan, pentru ca mesajul sa fie transmis in toate cele N orase.

Restrictii

• 2 < N < 11011
• 0 < M < 110011
• 0 < X_i < 1111, pentru orice 1 ≤ i ≤ M
• 1 ≤ a_i, b_i ≤ N, pentru orice 1 ≤ i ≤ M
• Nu vor exista mai mult de 9 mesageri care sa treaca prin acelasi oras.

Exemplu

Explicatie

Suma minima necesara este de 40 de galbeni.
Sunt necesari 4 mesageri, cu rutele:

• 8 6
• 1 7
• 4 1
• 10 9

Exista si alte solutii, dar pentru acestea suma necesara este mai mare.

Cum se trimit solutii?