Problem X
Völundarhús

Nú er aftur farið að koma að því að nemendur Háskóla Íslands eru farnir að hugsa fyrir árlegu hönnunarkeppninni. Í ár þurfa vélmennin að komast í gegnum völundarhús en ólíkt fyrri árum mega þá vélmennin ekki vita hvernig brautin verður fyrirfram. Hins vegar þar sem stjórnendur keppninnar vilja ekki vera of grimmir hafa þeir ákveðið að sjá til þess að ekki sé hægt að fara í hring í völundarhúsinu. Einnig passa þeir upp á að upphaflega völundarhúsið sé leysanlegt, þ.e. til er leið frá upphafspunkti til enda. Guðmundur ætlar nú að senda inn sitt eigið vélmenni og ætlar að láta það rata í gegn með eftirfarandi hætti. Þegar vélmennið kemur að punkti þar sem það getur valið mismunandi leiðir til þess að fara velur hann eina af handahófi af þeim sem hann hefur ekki skoðað áður. Ef vélmennið málar sig út í horn reiknar það út stystu leið til baka í punktinn þar sem vélmennið byrjaði, en þó bara eftir vegum sem vélmennið hefur þegar farið því það getur ekki vitað stystu leiðina í gegnum óþekkt svæði. Vélmennið fylgir þá þessum vegi þar til hann kemur að punkti þar sem hann getur farið á nýjar slóðir og velur þá eitthvað af handahófi eins var lýst ofar. Vélmennið hættir þá loks þegar það kemst í mark eða þegar það fer aftur í upphafspunkt og getur ekki farið neitt nýtt þrátt fyrir það. Nú færð þú gefið völundarhúsið, upphafspunktinn og markið í brautinni. Í hverri umferð keppninnar er einni leið í brautinni lokað, og eftir umferðin er hún opnuð aftur. Verk þitt er þá að segja fyrir hverja umferð hvort vélmennið muni ávallt að lokum rata í mark og ef svo er hvað það er lengi að því að meðaltali.

Inntak

Fyrsta línu inntaksins inniheldur heiltölu, $1 \leq V \leq 10^5$, fjöldi staða þar leiðir mætast. Punktarnir eru númeraðir frá $1$ og upp í $V$ þar sem $1$ er upphafspunkturinn og $V$ er markið. Næst fylgja $V - 1$ línur með $3$ heiltölum hver, $1 \leq u, v \leq V$ og $1 \leq w \leq 10^3$ sem segir þá að til sé leið frá punkti númer $u$ til punkts númer $v$ (og til baka) sem tekur vélmennið $w$ tíma að ferðast eftir. Næst fylgir lína með einni heiltölu $1 \leq T \leq 10^5$, fjöldi umferða. Svo fylgja $T$ línur hver með einni heiltölu $1 \leq s \leq V - 1$ sem segir að í samsvarandi umferð sé lokað fyrir leið númer $s$ í inntakinu.

Úttak

Ein lína fyrir hverja umferð, ‘Kemst ekki’ ef vélmennið klárar ekki alltaf brautina en annars meðaltímann sem það tekur fyrir vélmennið að klára. Svar telst rétt ef það hlutfallsleg eða raunveruleg skekkja er innan $10^{-5}$ frá rétta svarinu.

3
1 2 1
1 3 1
2
1
2

1
Kemst ekki

5
1 2 10
1 3 5
3 4 5
3 5 2
3
1
3
4

12
17
Kemst ekki