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 \le i \le 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.

The first line of input will contain two integers n,q (2 \le n,q \le 200000), the number of nodes, and the number of queries, respectively.

The next 2n-2 integers will contain 3 integers ai,bi,ci, denoting a directed edge from node ai to node bi with weight ci.

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 bi=1.

More specifically,
The edges (a1,b1),(a2,b2),... (an-1,bn-1) will describe a rooted spanning tree pointing away from node 1. bj=1 for n \le j \le 2n-2. an,an+1,...,a2n-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.

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