Problem B
Leiðinda rigning

Atli er að reyna komast heim, en eins og flesta daga er hellidemba í höfuðborginni. Hann er því að reyna skipuleggja ferðir sínar svo hann ferðist sem minnst um í rigningunni. Nánar tiltekið er hann búinn að finna $n$ skjól sem hann getur látið sig þorna undir. Milli þessarra skjóla verða $m$ leiðir og fyrir hverja leið verður gefið hvað Atli blotnar mikið við að fara þá leið. Þar til viðbótar verða einhver þessarra skjóla strætóstöð. Til að komast heim þarf Atli því að ferðast milli skjóla þar til hann kemst í strætóstöð og getur þaðan tekið strætó alla leið heim. Atli velur ávallt leiðina sem lágmarkar hversu blautur hann verður í mesta lagi á leiðinni.

Atli er ekki alltaf að ferðast milli sömu staða og einnig eru strætóstöðvar ekki meitlaðar í stein heldur. Því munu vera $q$ fyrirspurnir, hver af einum af þremur gerðum. Fyrirspurn getur sagt að eitthvert skjól sé gert að strætóstöð, sagt að eitthvað skjól sé ekki lengur strætóstöð eða beðið um að prenta hversu blautur Atli verður í mesta lagi á leiðinni heim frá einhverju tilteknu skjóli. Í byrjun er skýli $1$ eina strætóstöðin.

Atli er auðvitað löngu búinn að leysa þetta sjálfur, en segir engum frá lausninni því það myndi skemma fjörið.

Inntak

Inntak byrjar á einni línu með tveimur heiltölum $1\le n\le 5\cdot {10}^4$, fjöldi skjóla, og $0\le m\le {10}^5$, fjölda leiða milli skjóla. Næst koma $m$ línur þar sem hver lína lýsir leið milli skjóla. Hver slík lína inniheldur þrjár heiltölur $1\le a,b\le n$ og $0\le w\le {10}^9$. Þetta merkir að til sé leið frá skjóli $a$ til $b$ sem Atli blotnar um $w$ við að ferðast eftir. Ferðast má eftir leiðinni í báðar áttir og Atli blotnar jafn mikið sama í hvora átt er farið. Næst kemur lína með einni heiltölu $1\le q\le 5\cdot {10}^4$, fjölda fyrirspurna. Loks koma svo $q$ línur, hver með einni fyrirspurn. Hver slík lína inniheldur tvær heiltölur $1\le t\le 3$ og $1\le x\le n$. Ef $t=1$ merkir þetta að strætóstöð sé byggð við skjól $x$, gefið er að þá hafi ekki verið strætóstöð þar áður. Ef $t=2$ merkir þetta að ekki sé lengur strætóstöð við skjól $x$, gefið er að þetta sé strætóstöð og að $x\ne 1$. Loks ef $t=3$ skal prenta hversu blautur Atli verður við að komast heim úr skjóli $x$.

Gefið er að alltaf verði hægt að komast milli allra skjóla. Einnig verður alltaf að minnsta kosti ein strætóstöð að hverju sinni.

Úttak

Prenta skal hversu blautur Atli verður í mesta lagi í hverri fyrirspurn með $t=3$.

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

4
2
1
0
4