Diverging Directions

3000ms

262144K

Description:

You are given a directed weighted graph with n nodes and 2n - 2 edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to 2n - 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.

Input:

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 2n - 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₁, b₁), (a₂, b₂), ... (a_n - 1, b_n - 1) will describe a rooted spanning tree pointing away from node 1.
b_j = 1 for n ≤ j ≤ 2n - 2.
a_n, a_n + 1, ..., a_2n - 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 10⁶.

Output:

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

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF838B