问题描述

给定一棵有 $N$ 个顶点的树 $T$。边 $i$ $(1 \leq i \leq N-1)$ 连接顶点 $u_i$ 和 $v_i$，并具有权重 $w_i$。

按顺序处理 $Q$ 个查询。查询有两种类型，如下所示。

• 1 i w：将边 $i$ 的权重更改为 $w$。
• 2 u v：打印顶点 $u$ 和顶点 $v$ 之间的距离。

这里，一棵树上两个顶点 $u$ 和 $v$ 之间的距离是连接它们的路径上所有边的权重之和的最小值。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$ $(1 \leq i \leq N-1)$
• $1 \leq w_i \leq 10^9$ $(1 \leq i \leq N-1)$
• 给定图是一棵树。
• $1 \leq Q \leq 2 \times 10^5$
• 对于每个第一类查询，
  • $1 \leq i \leq N-1$，且
  • $1 \leq w \leq 10^9$。
• 对于每个第二类查询，
  • $1 \leq u, v \leq N$。
• 至少有一个第二类查询。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$ $w_{N-1}$ $Q$ $query_1$ $query_2$ $\vdots$ $query_Q$

这里，$query_i$ 表示第 $i$ 个查询，并且有以下一种格式之一：

$1$ $i$ $w$ $2$ $u$ $v$

输出

打印 $q$ 行，其中 $q$ 是第二类查询的数量。第 $j$ 行 $(1 \leq j \leq q)$ 应包含第 $j$ 个第二类查询的答案。

示例输入 1

5
1 2 3
1 3 6
1 4 9
4 5 10
4
2 2 3
2 1 5
1 3 1
2 1 5

示例输出 1

9
19
11

初始树如下图所示。

应按以下方式处理每个查询。

• 第一个查询要求你打印顶点 $2$ 和顶点 $3$ 之间的距离。依次经过边 $1$ 和边 $2$ 的路径构成了它们之间的一条路径，总权重为 $9$，是最小值，因此应打印 $9$。
• 第二个查询要求你打印顶点 $1$ 和顶点 $5$ 之间的距离。依次经过边 $3$ 和边 $4$ 的路径构成了它们之间的一条路径，总权重为 $19$，是最小值，因此应打印 $19$。
• 第三个查询将边 $3$ 的权重更改为 $1$。
• 第四个查询要求你打印顶点 $1$ 和顶点 $5$ 之间的距离。依次经过边 $3$ 和边 $4$ 的路径构成了它们之间的一条路径，总权重为 $11$，是最小值，因此应打印 $11$。

示例输入 2

7
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
3
2 1 6
1 1 294967296
2 1 6

示例输出 2

5000000000
4294967296

注意，答案可能不适合 $32$ 位整数。

示例输入 3

1
1
2 1 1

示例输出 3

0

示例输入 4

8
1 2 105
1 3 103
2 4 105
2 5 100
5 6 101
3 7 106
3 8 100
18
2 2 8
2 3 6
1 4 108
2 3 4
2 3 5
2 5 5
2 3 1
2 4 3
1 1 107
2 3 1
2 7 6
2 3 8
2 1 5
2 7 6
2 4 7
2 1 7
2 5 3
2 8 6

示例输出 4

308
409
313
316
0
103
313
103
525
100
215
525
421
209
318
519