← 返回题目列表

Codeforces · 838/B

B. 发散方向

中文机器翻译题面 查看原题

给您一个有 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