Grapevine

문제

Syrup the Turtle waters the huge Grapevine which snakes around town. The layout of the Grapevine can be best described as having $NN$ leafy joints, which Syrup has numbered $11$ to $NN$, connected by $N-1N\; -\; 1$ branches also numbered $11$ to $N-1N\; -\; 1$. Each branch $ii$ directly connects two joints $A_{i}A\_i$ and $B_{i}B\_i$, and has a length of $W_{i}W\_i$. No two branches directly connect the same pair of joints, and as part of the single Grapevine, every joint is connected to every other either directly or indirectly by branches.

With his sturdy hose and a little handiwork, Syrup is able to sway the growth of the Grapevine as he deems fit. In particular, he can soak a joint of the vine - causing it to immediately sprout a single giant grape if it was empty, or instead dislodging the grape there if one was present.

He can also anneal a branch with water, extending or shortening it to a new length $w_{i}w\_i$ by spraying at the right pressure and angle. To make sure things are on track, Syrup will periodically stand atop an elevated joint and seek for the closest grape. The distance from such a joint to a grape is defined by the shortest path starting from said joint, traversing a number of branches (or none at all), and ending at the grape’s own joint.

Right now, the Grapevine has no grapes attached after the last passing storm. Syrup has his watering agenda of $QQ$ actions planned out for the week and is about to begin spraying; but first, he needs to know what distances to expect when he seeks for grapes along the way. Given Syrup’s watering plans, your task is to find for each planned seek the distance from the specified joint to the nearest grape.

입력

Your program must read from standard input.

The first line contains two integers, $NN$ and $QQ$.

$N-1N\; -\; 1$ lines will follow. The $ii$^th line contains three integers, $A_{i}A\_i$, $B_{i}B\_i$, and $W_{i}W\_i$, describing a single branch.

$QQ$ lines will follow, each representing an action by Syrup.

• If the first integer of the line is $11$, it represents a seek and $11$ integer $q_{i}q\_i$ will follow. This means that you are to determine the distance between joint $q_{i}q\_i$ and the nearest joint with a grape, and output this distance. If there are no grapes on the Grapevine, output $-1-1$ instead.
• If the first integer of the line is $22$, it represents a soak and $11$ integer $u_{i}u\_i$ will follow. This means that joint $u_{i}u\_i$ is soaked and grows a grape or has its grape dislodged.
• If the first integer of the line is $33$, it represents an anneal and $33$ integers $a_{i}a\_i$, $b_{i}b\_i$, and $w_{i}w\_i$ will follow. This means that the length of the branch between joints $a_{i}a\_i$ and $b_{i}b\_i$ has had its length changed to $w_{i}w\_i$. It is guaranteed that a branch between joints $a_{i}a\_i$ and $b_{i}b\_i$ exists.

출력

Your program must print to standard output.

For each seek action, output one line with a single integer, the distance to the closest grape, or $-1-1$ if no grapes are present.

7 11
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 6
2 4
2 7
1 1
3 2 3 0
1 1
3 6 5 0
1 1
3 3 5 0
3 2 4 0
1 1

11
8
8
2

6 11
1 2 3
1 3 4
2 4 1
2 5 4
3 6 6
2 3
1 2
2 4
3 1 3 2
1 1
2 3
3 2 1 2
2 4
1 3
2 2
1 3

7
2
-1
4

7 8
1 2 2
2 3 3
3 6 2
4 6 1
5 6 4
6 7 3
2 3
1 4
2 3
2 5
1 1
3 6 7 4
1 5
1 7

3
11
0
8