乌龟 Syrup 正在照料镇上蜿蜒盘绕的巨大葡萄藤（Grapevine）。葡萄藤的布局可以描述为拥有 $N$ 个叶状节点，Syrup 将其编号为 $1$ 到 $N$，并由 $N-1$ 条同样编号为 $1$ 到 $N-1$ 的分支连接。每条分支 $i$ 直接连接两个节点 $A_i$ 和 $B_i$，长度为 $W_i$。任意两个节点之间不存在多条直接连接的分支，且作为单一葡萄藤的一部分，每个节点都可以通过分支直接或间接地连接到其他所有节点。

凭借他坚固的水管和一点手工活，Syrup 可以随心所欲地改变葡萄藤的生长。具体来说，他可以浸泡（soak）藤蔓上的一个节点——如果该节点为空，它会立即长出一颗巨大的葡萄；如果该节点已经有葡萄，则会将葡萄移除。

他还可以用水退火（anneal）一条分支，通过以合适的压力和角度喷水，将其延长或缩短至新的长度 $w_i$。为了确保一切按计划进行，Syrup 会定期站在一个高处的节点上，寻找（seek）距离最近的葡萄。从这样一个节点到葡萄的距离定义为从该节点出发，经过若干条分支（或不经过分支），到达葡萄所在节点的最短路径长度。

目前，在经历上次风暴后，葡萄藤上没有任何葡萄。Syrup 已经为本周规划了 $Q$ 个浇水动作，并准备开始喷水；但首先，他需要知道在寻找葡萄的过程中会遇到什么样的距离。给定 Syrup 的浇水计划，你的任务是针对每次计划的寻找操作，找出从指定节点到最近葡萄的距离。

输入格式

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

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

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

接下来 $Q$ 行，每行代表 Syrup 的一个动作。

• 如果该行第一个整数为 $1$，则代表一次寻找（seek）操作，随后跟一个整数 $q_i$。这意味着你需要确定节点 $q_i$ 与最近的葡萄所在节点之间的距离，并输出该距离。如果葡萄藤上没有葡萄，则输出 $-1$。
• 如果该行第一个整数为 $2$，则代表一次浸泡（soak）操作，随后跟一个整数 $u_i$。这意味着节点 $u_i$ 被浸泡，长出一颗葡萄或其上的葡萄被移除。
• 如果该行第一个整数为 $3$，则代表一次退火（anneal）操作，随后跟三个整数 $a_i, b_i$ 和 $w_i$。这意味着节点 $a_i$ 和 $b_i$ 之间的分支长度被更改为 $w_i$。保证节点 $a_i$ 和 $b_i$ 之间存在一条分支。

输出格式

程序必须打印到标准输出。

对于每次寻找操作，输出一行，包含一个整数，即到最近葡萄的距离；如果不存在葡萄，则输出 $-1$。

数据范围

最大执行时间为 3.0 秒。对于所有测试用例，输入满足以下限制：

• $2 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le A_i \neq B_i \le N$
• $0 \le W_i \le 10^9$

你的程序将在满足以下限制的输入实例上进行测试：

样例

输入格式 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

输出格式 1

11
8
8
2

说明 1

在第一次寻找中，最近的葡萄位于节点 4，路径为 $1 \to 2 \to 4$，距离为 $2 + 9 = 11$。第二次寻找中，最近的葡萄位于节点 7；第三次寻找中，节点 6 和 7 上的葡萄距离相等且最近。第四次（最后一次）寻找中，最近的葡萄位于节点 4。

输入格式 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

输出格式 2

7
2
-1
4

输入格式 3

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

3
11
0
8