In România anilor 2100 structura interna a companiilor a "evoluat" în asa fel încât fiecare angajat nu are doar un sef. Angajatul poate avea mai multi sefi sau nici unul. Totusi un lucru înca se pastreaza. Mergând pe orice lant de sefi nimeni nu este propriul sau sef.

Ca în orice companie, uneori apar divergente de opinii care sunt mediate de seful comun. Acuma însa o pereche de angajati nu are doar un sef. Dupa câtiva ani de experimentari s-a ajuns la concluzia ca cel mai bine este sa se apeleze la un singur sef si anume cel care poate lua o decizie si o poate comunica angajatilor aflati în conflict cel mai repede. Din fericire în România deciziile se iau imediat, însa din nefericire comunicarea deciziilor luate se face foarte greu.

Astfel comunicarea se face numai între angajati pentru care exista o subordonare directa. Fiecare astfel de comunicare are un timp asociat, iar comunicarea deciziei catre cei 2 angajati se face pe rând. Adica se asteapta pâna când unul dintre angajati a aflat de decizie si dupa aceea se începe comunicarea catre al doilea angajat.

Cerinta
Date fiind relatiile dintre angajati si durata comunicarii unei decizii pentru fiecare astfel de relatie se cere determinarea timpului minim pentru a ajunge la un compromis, pentru mai multe perechi de angajati.

Date de intrare
Fisierul de intrare conflicte.in contine pe prima linie trei numere naturale nenule N, M si Q, reprezentând numarul de angajati, numarul de relatii directe de subordonare si numarul de perechi de angajati aflati în conflict.
Pe urmatoarele M linii se afla câte 3 numere: S, D, C reprezentând o relatie directa de subordonare: seful S, subordonatul D si costul comunicarii unei decizii C.
Angajatii sunt numerotati de la 1 la N.
Pe urmatoarele Q linii se afla câte doua numere întregi, reprezentând perechi de angajati care se afla în conflict.

Date de iesire
Fisierul de iesire conflicte.out contine Q linii. Pe linia i este scris un numar intreg reprezentând costul minim pentru rezolvarea conflictului dintre angajatii din cea de a i-a pereche (consdierand ordinea perechilor din fisierul de intrare) sau valoarea -1, daca pentru angajatii din perechea i nu exista un sef comun.

Restrictii si precizari
1 <= N <= 1 000
1 <= M <= 50 000
1 <= Q <= 50 000
0 <= C <= 1 000
între orice pereche de angajati exista maxim o relatie de subordonare directa.

Exemplu

Marius Andrei
Google Inc
marsamg@yahoo.com