Kyselyt

• Time limit: 1.00 s
• Memory limit: 128 MB

Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ tietä. Tehtäväsi on vastata kyselyihin, mikä on lyhin reitti kaupungista toiseen.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $q$: kaupunkien määrä, teiden määrä ja kyselyiden määrä.

Sitten syötteessä on $m$ riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: kaupunkien $a$ ja $b$ välillä on tie, jonka pituus on $c$. Kaikki tiet ovat kaksisuuntaisia.

Lopuksi syötteessä on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: reitin tulee kulkea kaupungista $a$ kaupunkiin $b$.

Tuloste

Tulosta jokaiseen kyselyyn, kuinka pitkä on lyhin reitti kaupunkien välillä. Jos kaupunkien välillä ei ole mitään reittiä, tulosta "QAQ".

Rajat

• $1 \le n \le 500$
  
• $1 \le m \le n^2$
  
• $1 \le q \le 10^5$
  
• $1 \le a,b \le n$
  
• $1 \le c \le 10^9$
  

Esimerkki

Syöte:
4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Tuloste:
5
5
8
QAQ
3