Fişierul intrare/ieşire:	tollroads.in, tollroads.out	Sursă	ad-hoc
Autor		Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	1.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

TollRoads

N oraşe sunt conectate între ele prin M autostrăzi bidirecţionale, fiecare autostradă (a, b) având un cost de tranzit $c$ ataşat. Se doreşte revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul şi necesită investigaţie, deoarece o parte dintre cele N oraşe sunt centre comerciale sau turistice importante.

Cerinţă

Se doreşte să se afle răspunsul la o serie de Q$ întrebări de forma: $(X, T) - câte dintre celelalte N-1 oraşe, au acces către oraşul X, cu o taxă totală de cel mult T către fiecare oraş?

Date de intrare

Fişierul de intrare tollroads.in conţine pe primul rând numerele N, M şi Q reprezentând numărul de oraşe, numărul de autostrăzi şi numărul de interogări. Pe fiecare din următoarele M rânduri sunt scrise câte trei numere a, b, c, separate prin câte un spaţiu, reprezentând două oraşe între care există o autostradă şi costul autostrăzii. Pe următoarele Q rânduri se află scrise câte două numere X şi T, separate prin spaţiu, reprezentând datele interogărilor, conform enunţului.

Date de ieşire

În fişierul de ieşire tollroads.out se vor scrie pe fiecare dintre primele Q rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.

Restricţii

• 1 ≤ N ≤ 10^5
• 1 ≤ M ≤ 10^5
• 1 ≤ a, b ≤ N
• 1 ≤ c ≤ 10^5
• 1 ≤ T ≤ 10^5
• 1 ≤ Q ≤10^2
• între orice două oraşe poate exista mai mult de o autostradă

Exemplu

Explicaţie

Oraşele 2,3,4,5,6,7 au acces către oraşul 1 cu taxă maximă 6
Oraşele 2,3,4,5,6 au acces către oraşul 1 cu taxă maximă 5
Oraşele 2,3,5 au acces către oraşul 1 cu taxă maximă 4
Oraşele 1,3,5 au acces către oraşul 2 cu taxă maximă 3
Oraşele 2,3,5,6,7 au acces către oraşul 4 cu taxă maximă 4

Cum se trimit solutii?