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

Timp maxim de executie/test: 1.4 secunde
Memorie totala disponibila: 20 MB, din care 1 MB pentru stiva.

Marius Andrei
Google Inc
marsamg@yahoo.com