题目描述

给出一个 $n$ 个点，$2n-2$ 条边的带权有向图。边分为两类：

1. 前 $n-1$ 条边构成一棵生成树，$1$ 为其根结点，每条边从父亲连向儿子。
2. 后 $n-1$ 条边从 $i$ 号结点连向 $1$ 号结点，$2\le i\le n$。

有 $m$ 次操作：

• 1 i w：将第 $i$ 条边的边权改为 $w$。
• 2 u v：查询 $u$ 到 $v$ 的最短路。

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 2\times 10^5$。

接下来 $2n-2$ 行，每行三个整数 $a_i,b_i,c_i$，表示从 $a_i$ 到 $b_i$ 存在一条边权为 $c_i$ 的有向边，任意时刻边权 $\le 10^6$。

输出格式

对于每个操作 $2$，在一行中输出一个整数表示答案。

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

0
1
4
8
100
132
10