题目描述

Syrup 有一个巨大的葡萄藤。这个葡萄藤上共有 $N$ 片叶子，用 $1 \sim N$ 编号；这些叶子之间有 $N-1$ 条藤连接。第 $i$ 条藤连接第 $A_i$ 和第 $B_i$ 片叶子，长度为 $W_i$。换句话说，这些叶子和藤组成了一棵树。没有两个葡萄藤的两端相同，且这些叶子之间都可以相互到达。

Syrup 精通养护葡萄藤。他可以向一个叶子 $j$ 浇水，使得这里飞速生长。如果这片叶子上还没有葡萄，那么浇完水后会立刻长出；如果已经有葡萄了，那么这个葡萄会因为水分过多而消失。

他也可以选择一条树枝，并改变它的长度。因为这个葡萄藤实在太大了，所以他需要站在叶子上，并快速找到离它距离最近的一个葡萄。

现在，刚刚经历过暴风雨的葡萄藤上没有葡萄。在这一周内，Syrup 打算进行 $Q$ 次以上操作，他想让你帮他快速回答出他的问题。

输入格式

第一行，两个整数 $N,Q$；

接下来 $N-1$ 行，每行三个整数 $A_i,B_i,W_i$。

接下来 $Q$ 行，表示 $Q$ 个操作：

• 1 q：现在 Syrup 站在编号为 $q$ 的叶子上，他想找到离它最近的葡萄，请你输出这个最小距离。

• 2 u：向编号为 $u$ 的叶子浇水。

• 3 a b w：将第 $a$ 片叶子和第 $b$ 片叶子之间的树枝长度改为 $w$。

输出格式

对于每个 1 操作，输出距离的最小值。如果当前没有任何一个葡萄，输出 -1。

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

提示

【数据范围】

对于 $100\%$ 的数据，$2 \le N \le 100000,1 \le Q \le 100000,1 \le A_i \not = B_i \le N,0 \le W_i \le 10^9$。