Problem B
Leiðinda rigning

Atli is trying to get home, but like most days it’s raining cats and dogs in Reykjavík. Thus he is trying to plan his route such that he’ll minimize how wet he gets. More specifically he has located $n$ shelters from the rain which he can let himself dry under. He has also located $m$ routes between these shelters and for each route he has figured out how wet he’ll get travelling that route. Additionally some of these shelters will be bus stops. To get home Atli has to travel between shelters until he gets to a bus stop, from which he can travel all the way home. Atli will always travel home in a way that minimizes how wet he gets along the way.

Atli isn’t always travelling from the same place and bus stops aren’t set in stone either. Thus there will be $q$ queries, each one being one of three types. A query can say that a particular shelter is now a bus stop, say that a particular shelter is no longer a bus stop or ask for how wet Atli will get travelling home from some particular shelter. At the start only shelter $1$ is a bus stop.

Atli solved this problem long ago of course, but he won’t tell anyone the solution since that would spoil the fun.

Input

The first line of the input contains two integers $1\le n\le 5\cdot {10}^4$, the number of shelters and $0\le m\le {10}^5$, the number of routes between them. Next there are $m$ lines, each describing a route between two shelters. Each of those lines contains three integers $1\le a,b\le n$ and $0\le w\le {10}^9$. This means there is a route from shelter $a$ to shelter $b$ which makes Atli $w$ wet from travelling along it. Routes can be travelled in either direction and $w$ does not change depending on the direction. Next there is a line with an integer $1\le q\le 5\cdot {10}^4$, the number of queries. Finally there are $q$ lines, each containing two integers $1\le t\le 3$ and $1\le x\le n$. If $t=1$ this means that a bus stop opens at shelter $x$, in this case $x$ will not already be a bus stop. If $t=2$ this means that the bus stop at shelter $x$ closes, in this case $x$ will be a bus stop. Finally if $t=3$ the program should print how wet Atli gets at most when travelling home from shelter $x$.

It is guaranteed that it will always be possible to travel from any shelter to any other. Furthermore there will always be at least one working bus stop at any given time.

Output

How wet Atli gets should be printed for every query of type $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