【题目描述】

给定一个有 $n$ 个点、$2n-2$ 条边的有向带权图，点编号为 $1$ 到 $n$，边编号为 $1$ 到 $2n-2$。

这些边分为两部分：

• 前 $n-1$ 条边形成一棵以 $1$ 为根的有向生成树，边的方向均从根指向子结点；
• 后 $n-1$ 条边分别从某个结点 $i$ 指向结点 $1$，其中 $2 \le i \le n$，并且这些起点两两不同，恰好覆盖所有 $2$ 到 $n$ 的结点。

接下来需要处理 $q$ 个询问，询问有两种：

• 1 i w：将第 $i$ 条边的权值修改为 $w$；
• 2 u v：询问从结点 $u$ 到结点 $v$ 的最短路径长度。

请对所有第二类询问输出答案。

【输入格式】

第一行输入两个整数 $n,q$，表示结点数和询问数。

接下来 $2n-2$ 行，每行三个整数 $a_i,b_i,c_i$，表示第 $i$ 条边是一条从 $a_i$ 指向 $b_i$，权值为 $c_i$ 的有向边。

前 $n-1$ 条边构成一棵从根 $1$ 向外连出的有根生成树。后 $n-1$ 条边满足 $b_i=1$，并且对应的 $a_i$ 两两不同，均在 $2$ 到 $n$ 之间。

接下来 $q$ 行，每行三个整数，描述一次询问，格式如题目描述所示。

【输出格式】

对于每个第二类询问，输出一行一个整数，表示从 $u$ 到 $v$ 的最短路径长度。

【样例输入】

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

【提示】

数据范围：$2 \le n,q \le 200000$，所有边权均在 $1$ 到 $10^6$ 之间。