== include(page="template/taskheader" task_id="radiatie") ==

Zaharel este cercatator de fizica nucleara si lucreaza la un complex de cercetare secret format din $N$ laboratoate, numerotate convenabil cu numere de la $1$ la $N$. De asemenea, aceste laboratoare sunt conectate prin $M$ tunele bidirectionale, de diverse lungimi. Desi laboratoarele sunt concepute astfel incat cercetatorii sa nu fie expusi la radiatii, tunelele nu protejeaza complet, astfel incat daca un cercetator foloseste un anumit tunel de legatura va fi expus la un nivel de radiatii direct proportional cu lungimea tunelului.
Zaharel are de efectuat $K$ drumuri intre diverse perechi de laboratoare. Stiind ca expunerea pentru un timp indelungat la radiatii are efecte daunatoare, el va alege mereu un drum in care lungimea maxima a unui tunel parcurs este minima. Determinati care vor fi drumurile pe care le va alege Zaharel.

...

h2. Date de intrare

Prima linie a fisierului de intrare $radiatie.in$ va contine numerele naturale $N, M, K$ separate prin spatii. Urmatoarele $M$ linii vor contine cate trei numere naturale $a b c$ cu semnificatia ca exista un tunel intre laboratorul cu numar $a$ si laboratorul cu numar $b$, de lungime $c$. In continuare, urmatoarele $K$ linii vor contine perechi de numere naturale $x y$ avand semnificatia ca Zaharel va efectua un drum intre laboratoarele $x$ si $y$.

...

h2. Date de iesire

Fisierul de iesire $radiatie.out$ va contine $K$ linii, fiecare continand lungimea maxima minima considerand tunelele parcurse de Zaharel pentru fiecare drum. Rezultatele se vor afisa in ordinea in care sunt date cele $K$ drumuri in fisierul de intrare.

...

h2. Restrictii

* $1 ≤ N, K ≤ 15.000$
* $1 ≤ M ≤ 30.000$
* Lungimea unui tunel este un numar natural din intervalul $[1, 10^9^]$
* Un drum reprezinta o succesiune de laboratoare $a{~1~}, a{~2~} ... a{~x~}$ cu proprietatea ca exista un tunel intre $a{~i~}$ si $a{~i+1~}$ pentru orice $i < x$
* Se garanteaza ca exista cel putin un drum intre fiecare din cele $K$ perechi de laboratoare din fisierul de intrare

... ≤ ...

h2. Exemplu

table(example). |_. radiatie.in |_. radiatie.out |
| 6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
| 5
5
5
4
4
7
4
5

table(example). |_. radiatie.in |_. rRadiatie.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="radiatie") ==

1467