Šeštadieninė informatikos olimpiadininkų mokykla

Visoje Europoje dirbančios logistikos įmonės „Vienišiai“ (įmonė taip vadinasi, nes visi vairuotojai važinėja po vieną) vadybininkams labai svarbu greitai ir tiksliai atsakyti užsakovams, ar vairuotojai galės saugiai pervežti krovinį iš miesto į miestą .

Vairuotojų darbas yra atsakingas ir reikalauja budrumo, todėl jie privalo ne rečiau nei kas valandų pailsėti viešbutyje, kurių yra kiekviename mieste. Turėdami informaciją apie miestus ir juos jungiančius kelius, parašykite programą atsakysiančią į vadybininkų užklausas.

Pradiniai duomenys

Pirmoje eilutėje pateikti trys tarpais atskirti sveikieji skaičiai: - miestų skaičius, - kelių skaičius, - vadybininko pateiktų užklausų skaičius. Miestai numeruojami nuo iki .

Tolesnėse eilučių pateikta informacija apie kelius. Kiekvienoje eilutėje įrašyti trys tarpais atskirti sveikieji skaičiai: , ir , kurie nusako, kad nuvažiuoti tarp miestų ir užtrunka laiko. Keliai visada yra dvipusiai ir jais važiuoti abiem kryptimis užtrunka vienodai. Tarp dviejų miestų gali būti tik vienas tiesioginis kelias.

Paskutinėse eilučių pateikiamos vadybininkų užklausos. Kiekvienoje iš eilučių pateikiami du sveikieji skaičiai: - pradžios miesto numeris, - pabaigos miesto numeris..

Išvestis

Jūsų programa turi kiekvienai užklausai atskiroje eilutėje išvesti kiek mažiausiai laiko vairuotojas turi galėti važiuoti be poilsio, kad būtų galima saugiai pristatyti krovinį tarp miestų ir , arba , jeigu krovinio iš į pervežti neįmanoma.

Ribojimai

Visiems testams galios ribojimai , , .

Pavyzdžiai

5 3 3
1 3 9
2 4 2
3 5 8
1 5
3 4
2 4

9
-1
2