Problem S
Fimbulferð

Þetta vor, eins og mörg önnur, hefur haft sinn skerf af einstaklega köldum morgnum. Það er enginn veginn hægt að einbeita sér í tíma ef maður er upptekinn við að örvæntingarfullt reyna ná upp hita í fingrunum. Til að reyna koma í veg fyrir þennan vanda vantar að búa til forrit sem finnur hlýjustu leiðina milli bygginga! Þetta er eðlileg og skilvirk lausn á vandanum.

Inntak

Inntakið byrjar á einni línu með þremur heiltölum $1 \leq V, E \leq 5000$, $1 \leq Q \leq 10^5$. $V$ táknar fjölda bygginga á háskólasvæðinu, $E$ táknar fjölda gönguleiða milli bygginga og $Q$ táknar fjölda fyrirspurna um hlýjustu leiðina. Við númerum byggingarnar frá $1$ til $n$. Næstu $E$ línur lýsa einni gönguleið milli bygginga hver. Hver þeirra lína innihalda þrjár heiltölur $1 \leq a, b \leq V$, $-10^9 \leq t \leq 10^9$. Þetta merkir að til sé gönguleið frá byggingu númer $a$ í byggingu númer $b$ sem verður þess valdandi að maður kólni um $t$. Ef $t$ er neikvæð merkir það að manni hlýnar á leiðinni, t.d. ef er hægt að komast milli bygginganna innandyra. Ekki er endilega hægt að fara frá $b$ til $a$ þrátt fyrir að hægt sé að fara frá $a$ til $b$, t.d. ef ferðin felur það í sér að stökkva framan af svölunum á leiðinni. Loks koma $Q$ línur, hver með einni fyrirspurn. Hver þeirra lína inniheldur tvær heiltölur $1 \leq a, b \leq V$ og er þá verið að biðja um hlýjustu leiðina frá byggingu $a$ til byggingar $b$.

Úttak

Fyrir hverja fyrirspurn á að prenta hversu mikið maður kólnar á leiðinni í besta falli. Ef hægt er að hlýna er prentuð samsvarandi neikvæð tala. Ef ekki er hægt að komast á leiðarenda yfir höfuð skal í stað prenta engin leid. Ef hægt er að labba í hringi og hlýna eins mikið og manni sýnist áður en maður kemst á leiðarenda skal í stað prenta nogu hlytt.

8 10 3
1 2 10
2 3 -1
3 4 -1
4 2 -1
4 8 10
1 7 10
1 5 10
5 6 -20
6 7 10
7 8 10
1 7
1 8
8 1

0
nogu hlytt
engin leid