Problem: 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 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 ≤ j ≤ 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.

Output

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

Example

Input

5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4


Output

0
1
4
8
100
132
10

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
 
public class Main{
	static long INF=(long)1e18;
	static int n;
	static int []tin,tout,back,atTime;
	static long []dist1;
	static int timer;
	static ArrayList<edge>[]adj;
	static void dfs(int u,long d)
	{
		atTime[timer]=u;
		dist1[u]=d;
		tin[u]=timer++;
		
		for(edge nxt:adj[u])
			dfs(nxt.v,d+nxt.c);
		tout[u]=timer-1;
	}
	static boolean isAnc(int u,int v) {
		return tin[v]>=tin[u] && tout[v]<=tout[u];
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		n=sc.nextInt();
		int q=sc.nextInt();
		adj=new ArrayList[n];
		for(int i=0;i<n;i++)
			adj[i]=new ArrayList();
		
		int []to=new int [2*n],cost=new int [n];
		for(int i=1;i<n;i++)
		{
			int u=sc.nextInt()-1,v=sc.nextInt()-1,c=sc.nextInt();
			adj[u].add(new edge(v,c));
			to[i]=v;
			cost[i]=c;
		}
		back=new int [n];
		for(int i=1;i<n;i++)
		{
			int u=sc.nextInt()-1,v=sc.nextInt()-1,c=sc.nextInt();
			back[u]=c;
			to[i+n-1]=u;
		}
		tin=new int [n];
		tout=new int [n];
		atTime=new int [n];
		dist1=new long [n];
		dfs(0,0);
		
		SegmentTree tree=new SegmentTree();
		while(q-->0) {
			if(sc.nextInt()==1)
			{
				int idx=sc.nextInt(),w=sc.nextInt();
				if(idx>=n)
				{
					tree.updatePoint(to[idx], w);
				}
				else
				{
					int v=to[idx];
					int change=w-cost[idx];
					cost[idx]=w;
					tree.updateRange(tin[v], tout[v], change);
				}
				
			}
			else
			{
				int u=sc.nextInt()-1,v=sc.nextInt()-1;
				long ans=tree.queryPoint(v)-tree.queryPoint(u);
				if(!isAnc(u,v)) 
					ans+=tree.query(tin[u], tout[u]);
				
				out.println(ans);
			}
		}
		
		out.close();
 
	}
	static class edge
	{
		int v,c;
		edge(int y,int z){
			
			v=y;
			c=z;
		}
	}
	static class SegmentTree
	{
		long []lazy,dist,minTotal;
		SegmentTree()
		{
			lazy=new long [4*n];
			dist=new long [4*n];
			minTotal=new long [4*n];
			build(1,0,n-1);
		}
		void build(int node, int tl,int tr) {
			if(tl==tr)
			{
				dist[node]=dist1[atTime[tl]];
				minTotal[node]=dist[node]+back[atTime[tl]];
			}
			else
			{
				int mid=tl+tr>>1,left=node<<1,right=left+1;
				build(left,tl,mid);
				build(right,mid+1,tr);
				minTotal[node]=Math.min(minTotal[left], minTotal[right]);
			}
		}
		void updatePoint(int idx,int newBack)
		{
			back[idx]=newBack;
			updatePoint(1,0,n-1,tin[idx]);
		}
		void updatePoint(int node,int tl,int tr,int idx)
		{
			if(tl==tr)
				minTotal[node]=dist[node]+back[atTime[idx]];
			else
			{
				int mid=tl+tr>>1,left=node<<1,right=left+1;
				propagate(node);
				if(idx<=mid)
					updatePoint(left,tl,mid,idx);
				else
					updatePoint(right,mid+1,tr,idx);
				minTotal[node]=Math.min(minTotal[left], minTotal[right]);
 
		
			}
		}
		void updateRange(int l,int r,int change)
		{
			updateRange(1,0,n-1,l,r,change);
		}
		void updateRange(int node,int tl,int tr,int l,int r,int change) {
			if(r<tl || tr<l)
				return ;
			if(tl>=l && tr<=r)
			{
				lazy[node]+=change;
				minTotal[node]+=change;
				dist[node]+=change;
				return;
			}
			int mid=tl+tr>>1,left=node<<1,right=left+1;
			propagate(node);;
			updateRange(left,tl,mid,l,r,change);
			updateRange(right,mid+1,tr,l,r,change);
			minTotal[node]=Math.min(minTotal[left], minTotal[right]);
 
		}
		long queryPoint(int u) {
			return queryPoint(1,0,n-1,tin[u]);
		}
		long queryPoint(int node,int tl,int tr,int idx) {
			if(tl==tr)
				return dist[node];
			int mid=tl+tr>>1,left=node<<1,right=left+1;
			propagate(node);
			if(idx<=mid)
				return queryPoint(left,tl,mid,idx);
			else
				return queryPoint(right,mid+1,tr,idx);
			
		}
		void propagate(int node) {
			int left=node<<1,right=left+1;
			long x=lazy[node];
			lazy[left]+=x;
			lazy[right]+=x;
			minTotal[left]+=x;
			minTotal[right]+=x;
			dist[left]+=x;
			dist[right]+=x;
			lazy[node]=0;
		}
		long query(int l,int r) {
			return query(1,0,n-1,l,r);
		}
		long query(int node,int tl,int tr,int l,int r) {
			if(r<tl || tr<l)
				return INF;
			if(tl>=l && tr<=r)
				return minTotal[node];
			int mid=tl+tr>>1,left=node<<1,right=left+1;
			propagate(node);;
			return Math.min(query(left,tl,mid,l,r), query(right,mid+1,tr,l,r));
		}
		
	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}