Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

B. Diverging Directions
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 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 ≤ 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 106.

Output

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

Example
Input
5 91 3 13 2 21 4 33 5 45 1 53 1 62 1 74 1 82 1 12 1 32 3 52 5 21 1 1002 1 31 8 302 4 22 2 4
Output
014810013210