给您一个有 n 个节点和 2n - 2 条边的有向加权图。节点标记为 1 到 n,边标记为 1 到 2n - 2。图的边可以分为两部分。
- 前 n - 1 条边将形成一棵有根生成树,以节点 1 作为根。所有这些边都将指向远离根的方向。
- 对于所有 2 ≤ i ≤ n,最后 n - 1 条边将从节点 i 到节点 1。
您收到 q 个查询。有两种类型的查询
- 1 i w:将第i条边的权重改为w
- 2 u v:打印节点 u 到 v 之间的最短路径的长度
给定这些查询,打印最短路径长度。
输入
输入的第一行将包含两个整数 n、q (2 ≤ n, q ≤ 200 000)、节点数和查询数。
接下来的 2n - 2 个整数将包含 3 个整数 ai、bi、ci,表示从节点 ai 到节点 bi 的有向边,权重为 ci。
这些行的前 n - 1 行将描述指向远离节点 1 的有根生成树,而这些行的最后 n - 1 行将具有 bi = 1。
更具体地说,
- 边 (a1, b1), (a2, b2), ... (an - 1, bn - 1) 将描述指向远离节点 1 的有根生成树。
- bj = 1,n ≤ j ≤ 2n - 2。
- an, an + 1, ..., a2n - 2 将不同,且介于 2 和 n 之间。
接下来的 q 行将包含 3 个整数,以语句中描述的格式描述查询。
所有边权重都在 1 到 106 之间。
输出
对于每个类型 2 查询,在其自己的行中打印最短路径的长度。
示例
输入 #1
5 9 1 3 1 3 2 2 1 4 3 3 5 4 5 1 5 3 1 6 2 1 7 4 1 8 2 1 1 2 1 3 2 3 5 2 5 2 1 1 100 2 1 3 1 8 30 2 4 2 2 2 4
输出 #1
0 1 4 8 100 132 10