Până nu demult, în Bucovina existau doar N oraşe conectate între ele prin N-1 şosele bidirecţionale. Cu toate acestea, se putea ajunge din orice oraş în orice alt oraş mergând pe una sau mai multe şosele.
Când Ştefan trebuia să facă un anunţ important, el trimitea mesajul către fiecare dintre cei M mesageri ai săi. Fiecare mesager, după primirea mesajului de la Ştefan, pleacă să transmită mesajul primit pe o rută fixată. Mai exact, mesagerul i (1≤i≤M) va transmite mesajul în toate oraşele situate pe ruta care porneşte din oraşul ai şi ajunge în oraşul bi. Pentru a transmite mesajul în toate oraşele de pe ruta sa, mesagerul i (1≤i≤M) va primi Xi galbeni.
Cerinţă
Care este număr minim de galbeni pe care Ştefan trebuia să-l plătească pentru ca mesajul său să ajungă în toate cele N oraşe din Bucovina?
Date de intrare
Fişierul de intrare mesaj1.in conţine pe prima linie numărul natural N, reprezentând numărul de oraşe din Bucovina. Următoarele N-1 linii conţin câte două numere naturale distincte separate printr-un spaţiu a b cu semnificaţia ″există o şosea care conectează direct oraşele a şi b″. Pe linia N+1 este scris un număr natural M reprezentând numărul de mesageri. Pe următoarele M linii se află informaţii despre cei M mesageri. Pe cea de a i-a linie dintre cele M (1≤i≤M) sunt scrise trei numere naturale separate prin câte un spaţiu ai bi Xi, cu semnificaţia ″mesagerul i parcurge ruta de la oraşul ai la oraşul bi, fiind plătit cu Xi galbeni″.
Date de ieşire
Fişierul de ieşire mesaj1.out va conţine o singură linie pe care va fi scris numărul minim de galbeni pe care trebuie să-i plătească Ştefan, pentru ca mesajul să fie transmis în toate cele N oraşe.
Restricţii
2 < N < 11011
2 < M < 110011
0 < Xi < 1111, pentru orice 1≤i≤M
1 ≤ ai, bi ≤ N, pentru orice 1≤i≤M
Nu vor exista mai mult de 9 mesageri care să treacă prin acelaşi oraş.
Suma minimă necesară este de 40 de galbeni.
Sunt necesari 4 mesageri, cu rutele: 8 6
1 7
4 1
10 9
Există şi alte soluţii, dar pentru acestea suma necesară este mai mare.