h2. Date de intrare

Prima linie a fişierului de intrare $apm2.in$ va conţine pe prima sa linie cele trei numere $N$, $M$, si $Q$.

Prima linie a fişierului de intrare $apm2.in$ va conţine pe prima sa linie cele trei numere $N$, $M$, şi $Q$.

Fiecare dintre următoarele $M$ linii va descrie câte un drum prin trei numere întregi: $X$, $Y$, cele două oraşe legate de drumul respectiv şi $T$, taxa asociată acestuia.
Fiecare dintre următoarele $Q$ linii va descrie câte un drum adăugat de Marele Lider, prin două numere, $A$ şi $B$ reprezentând cele două oraşe legate de drumul respectiv.
h2. Date de ieşire

Fişierul de ieşire $apm2.out$ va conţine Q linii. Pe a $i$-a linie se va afla răspunsul întrebarea $'Care este cea mai mare taxă pe care o putem asocia celei de a $i$-a muchii ipotetice astfel incât aceasta să se afle sigur în arborele parţial de cost minim al reţelei?'$.

Fişierul de ieşire $apm2.out$ va conţine Q linii. Pe a $i$-a linie se va afla răspunsul întrebarea $'Care este cea mai mare taxă pe care o putem asocia celei de a $i$-a muchii ipotetice astfel încât aceasta să se afle sigur în arborele parţial de cost minim al reţelei?'$.

h2. Restricţii

* $1$ ≤ $M$ ≤ $100 000$
* $1$ ≤ $Q$ ≤ $1000$
* Se consideră că un drum apare $sigur$ în APM, dacă acesta apare în toate APM-urile posibile.

* Cele Q întrebări sunt independente unele de altele. Cu alte cuvinte, răspunsul pentru un anumit drum se calculeaza presupunând ca acesta este singurul drum adăugat celorlalte $M$ deja existente.

* Cele Q întrebări sunt independente unele de altele. Cu alte cuvinte, răspunsul pentru un anumit drum se calculează presupunând ca acesta este singurul drum adăugat celorlalte $M$ deja existente.

h2. Exemplu