mesaj

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 \leq i \leq M)$ va transmite mesajul în toate oraşele situate pe ruta care porneşte din oraşul $a_i$ şi ajunge în oraşul $b_i$. Pentru a transmite mesajul în toate oraşele de pe ruta sa, mesagerul $i\ (1 \leq i \leq M)$ va primi $X_i$ 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 mesaj.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 \leq i \leq M)$ sunt scrise trei numere naturale separate prin câte un spaţiu $a_i \ b_i \ X_i$, cu semnificaţia "mesagerul $i$ parcurge ruta de la oraşul $a_i$ la oraşul $b_j$, fiind plătit cu $X_i$ galbeni".

Date de ieșire

Fişierul de ieşire mesaj.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 și precizări

• $2 < N < 11 \ 011$
• $2 < M < 110 \ 011$
• $0 < X_i < 1 \ 111$, pentru orice $1 \leq i \leq M$
• $1 \leq a_i, b_i \leq N$, pentru orice $1 \leq i \leq M$
• Nu vor exista mai mult de $9$ mesageri care să treacă prin acelaşi oraş.

Exemplu

mesaj.in

10
1 2
1 3
3 4
3 5
5 6
5 7
5 8
2 9
2 10
9
8 6 10
10 9 10
1 4 30
4 1 10
7 8 50
1 7 10
6 1 10
10 1 10
9 1 10

mesaj.out

40

Explicație

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.