题目描述

译自 NOISG 2022 Final T4. Grapevine

乌龟西拉普在给环绕小镇的巨大葡萄藤浇水。葡萄藤的结构可以描述为有 $N$ 个叶状节点，编号从 $1$ 到 $N$，由 $N-1$ 条分支连接，分支编号也从 $1$ 到 $N-1$。每条分支 $i$ 直接连接两个节点 $A_i$ 和 $B_i$，长度为 $W_i$。没有两条分支直接连接相同的节点对，作为单一葡萄藤的一部分，每个节点通过分支直接或间接与其他节点相连。

凭借他坚固的水管和一些手工技巧，西拉普能够根据需要引导葡萄藤的生长。特别是，他可以浇灌一个节点，使其立即长出一颗大葡萄（如果该节点为空），或将已有的葡萄摘除（如果该节点已有葡萄）。

他还可以用水软化一条分支，通过以适当的压力和角度喷水，将其延长或缩短到新长度 $w_i$。为了确保一切顺利，西拉普会定期站在一个较高的节点上寻找最近的葡萄。从该节点到葡萄的距离定义为从该节点出发，穿过若干条分支（或无分支），到达葡萄所在节点的最短路径。

目前，葡萄藤在最近一次风暴后没有任何葡萄。西拉普计划了一周的 $Q$ 次浇水行动，即将开始喷水；但首先，他需要知道在寻找葡萄时预计的距离。给定西拉普的浇水计划，你的任务是为每次计划的寻找行动找出从指定节点到最近葡萄的距离。

输入格式

程序需从标准输入读取数据。

第一行包含两个整数 $N$ 和 $Q$。

接下来的 $N-1$ 行，第 $i$ 行包含三个整数 $A_i, B_i, W_i$，描述一条分支。

接下来的 $Q$ 行，每行表示西拉普的一次行动：

• 若行的第一个整数为 $1$，表示寻找行动，后面跟着一个整数 $q_i$。这意味着需要确定节点 $q_i$ 到最近的有葡萄的节点的距离，并输出该距离。若葡萄藤上没有葡萄，则输出 $-1$。
• 若行的第一个整数为 $2$，表示浇灌行动，后面跟着一个整数 $u_i$。这意味着节点 $u_i$ 被浇灌，长出一颗葡萄或摘除其现有葡萄。
• 若行的第一个整数为 $3$，表示软化行动，后面跟着三个整数 $a_i, b_i, w_i$。这意味着节点 $a_i$ 和 $b_i$ 之间的分支长度变为 $w_i$。保证节点 $a_i$ 和 $b_i$ 之间存在分支。

输出格式

程序需向标准输出输出结果。

对于每次寻找行动，输出一行，包含一个整数，表示到最近葡萄的距离；若没有葡萄，则输出 $-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

第一次寻找时，最近的葡萄在节点 $4$，路径为 $1 \to 2 \to 4$，距离为 $2 + 9 = 11$。

第二次寻找时，最近的葡萄在节点 $7$。

第三次寻找时，节点 $6$ 和 $7$ 的葡萄距离最近。

第四次也是最后一次寻找时，最近的葡萄在节点 $4$。

这个样例满足子任务 $1, 2, 5, 6$ 的限制。

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

这个样例满足子任务 $1, 3, 6$ 的限制。

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

这个样例满足子任务 $1, 4, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 100000$
• $1 \leq Q \leq 100000$
• $1 \leq A_i \neq B_i \leq N$
• $0 \leq W_i \leq 10^9$

详细子任务附加限制及分值如下表所示：