CF838B.Diverging Directions

You are given a directed weighted graph with n nodes and 2_n_ - 2 edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to 2_n_ - 2. The graph's edges can be split into two parts.

• The first n - 1 edges will form a rooted spanning tree, with node 1 as the root. All these edges will point away from the root.
• The last n - 1 edges will be from node i to node 1, for all 2 ≤ i ≤ n.

You are given q queries. There are two types of queries

• 1 i w: Change the weight of the i-th edge to w
• 2 u v: Print the length of the shortest path between nodes u to v

Given these queries, print the shortest path lengths.

给你一个包含 $n$ 个节点和 $2n-2$ 条有向带权边的图。节点编号为 $1$ 到 $n$，边编号为 $1$ 到 $2n-2$。该图的边可分为两部分：

• 前 $n-1$ 条边构成一棵以节点 $1$ 为根的有向生成树，且所有这些边均从根节点向外指向（即方向远离根节点）。
• 后 $n-1$ 条边则分别为从节点 $i$ 指向节点 $1$ 的边，其中 $2 \leq i \leq n$。

你将收到 $q$ 个查询，查询分为两类：

• 1 i w：将第 $i$ 条边的权重修改为 $w$；
• 2 u v：输出节点 $u$ 到节点 $v$ 的最短路径长度。

请根据这些查询，依次输出每次类型 2 查询所对应的最短路径长度。

The first line of input will contain two integers n, q (2 ≤ n, q ≤ 200 000), the number of nodes, and the number of queries, respectively.

The next 2_n_ - 2 integers will contain 3 integers a__i, b__i, c__i, denoting a directed edge from node a__i to node b__i with weight c__i.

The first n - 1 of these lines will describe a rooted spanning tree pointing away from node 1, while the last n - 1 of these lines will have b__i = 1.

More specifically,

• The edges (_a_1, _b_1), (_a_2, _b_2), ... (a__n - 1, b__n - 1) will describe a rooted spanning tree pointing away from node 1.
• b__j = 1 for n ≤ j ≤ 2_n_ - 2.
• a__n, a__n + 1, ..., a_2_n - 2 will be distinct and between 2 and n.

The next q lines will contain 3 integers, describing a query in the format described in the statement.

All edge weights will be between 1 and 106.

输入的第一行包含两个整数 $n$ 和 $q$（$2 \leq n, q \leq 200\,000$），分别表示节点数和查询数。

接下来的 $2n - 2$ 个整数将包含 $3$ 个整数 $a_i,\, b_i,\, c_i$，表示一条从节点 $a_i$ 指向节点 $b_i$、权重为 $c_i$ 的有向边。

其中前 $n-1$ 行描述一棵以节点 $1$ 为根、边方向远离根节点的有根生成树；后 $n-1$ 行则满足 $b_i = 1$。

更具体地：

• 边 $(a_1,\, b_1),\, (a_2,\, b_2),\, \dots,\, (a_{n-1},\, b_{n-1})$ 描述一棵以节点 $1$ 为根、边方向远离根节点的有根生成树；
• 对于 $n \leq j \leq 2n - 2$，均有 $b_j = 1$；
• $a_n,\, a_{n+1},\, \dots,\, a_{2n-2}$ 互不相同，且均在 $2$ 到 $n$ 之间（含端点）。

接下来的 $q$ 行每行包含 $3$ 个整数，描述一个如题面所述格式的查询。

所有边的权重均在 $1$ 到 $10^6$ 之间。

For each type 2 query, print the length of the shortest path in its own line.

对于每个类型 2 的查询，在单独一行中输出最短路径的长度。