Prima linie a fisierului de intrare contine numarul intreg $N$ iar pe fiecare din urmatoarele $N-1$ linii se vor afla informatii despre sistemul initial, pe linia $i$ aflandu-se doua numere intregi $K$ si $C$, reprezentand orasul cel mai apropiat de capitala de care este legat orasul $i$ si respectiv costul anual de intretine a strazii care leaga cele doua orase. Daca un oras e legat direct de capitala atunci $K=1$.

Linia $N+1$ contine numarul $M$ iar urmatoarele $M$ linii contin 3 numere intregi $X$,$Y$,$C$, care reprezinta faptul ca tocmai a fost construit un drum intre orasele $X$ si $Y$ care are costul anual de intretinere $C$.

Linia $N+1$ contine numarul $M$ iar urmatoarele $M$ linii contin 3 numere intregi $X$, $Y$, $C$, care reprezinta faptul ca tocmai a fost construit un drum intre orasele $X$ si $Y$ care are costul anual de intretinere $C$.

h2. Date de iesire

h2. Restrictii
* $1 ≤ N ≤ 50.000$

* $1 ≤ M ≤ 50.000$

* $1 ≤ M ≤ 150.000$

* costul anual de intretinere al oricarei strazi este un numar natural cel mult egal cu $1.000.000$
h2. Exemplu

3431