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:
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.math.*;
import java.util.*;

public class IndiaHacks {
	
	InputStream in;
	PrintWriter out;
	
	LazyPropagation lz;
	MinLazyPropagation mlz;
	void solve() {
		int n=ni();
		int q=ni();
        g=new ArrayList[n];
        for (int i=0;i<n;i++)
        	g[i]=new ArrayList<Edge>();
        Edge e[]=new Edge[2*n-2];
        
        for(int i=0;i<n-1;i++){
            int u=ni()-1;
            int v=ni()-1;
            long w=nl();
            g[u].add(new Edge(u,v,w));
            e[i]=new Edge(u,v,w);
        }
        
        for (int i=n-1;i<2*n-2;i++)
        {
        	int u=ni()-1;
        	int v=ni()-1;
        	long w=nl();
        	e[i]=new Edge(u,v,w);
        }
        
        preprocess(n, 0);
        
        lz=new LazyPropagation(time);
        mlz=new MinLazyPropagation(time);
        dfs2(0,0,0);

        for (int i=n-1;i<2*n-2;i++)
        {
        	
        	mlz.updateUtil(1, tin[e[i].u], tin[e[i].u], e[i].w);
        	mlz.updateUtil(1, tout[e[i].u], tout[e[i].u], e[i].w);
        }
        
        while(q-->0){
        	
            int t=ni();
       
            if(t==1){
            	int idx=ni();
            	long w=nl();
                if (idx<=n-1)
                {
                	idx--;
                	
                	lz.updateUtil(1, tin[e[idx].v], tout[e[idx].v], w-e[idx].w);
                	mlz.updateUtil(1, tin[e[idx].v], tout[e[idx].v], w-e[idx].w);
                	
                }
                else
                {
                	idx--;
                	mlz.updateUtil(1, tin[e[idx].u], tin[e[idx].u], w-e[idx].w);
                	mlz.updateUtil(1, tout[e[idx].u], tout[e[idx].u], w-e[idx].w);
                }
                e[idx].w=w;
            }
            else {
            	int v=ni()-1;
            	int u=ni()-1;
                int lca=lca(v, u);
                if (v==lca)
                {
                	long dis1=lz.queryUtil(1, tin[u], tin[u]);
                	long dis2=lz.queryUtil(1, tin[v], tin[v]);
                	long ans=dis1-dis2;
                	out.println(ans);
                }
                else if (u==lca)
                {
                	long dis1=lz.queryUtil(1, tin[u], tin[u]);
                	long dis2=lz.queryUtil(1, tin[v], tin[v]);
                	long min1=mlz.queryUtil(1, tin[v], tout[v])-dis2;
                	long ans=min1+dis1;
                	out.println(ans);
                }
                else
                {
                	long dis1=lz.queryUtil(1, tin[u], tin[u]);
                	long dis2=lz.queryUtil(1, tin[v], tin[v]);
                	long min2=mlz.queryUtil(1, tin[v], tout[v]-1)-dis2;
                	
                	long ans=min2+dis1;
                	out.println(ans);
                }
            }
        }
	}
	
	ArrayList<Edge>[] g;
	int len;
	int[][] up;
	int[] tin;
	int[] tout;
	int time;
	

	void dfs(int u, int p) {
		tin[u] = time++;
		up[0][u] = p;
		for (int i = 1; i < len; i++)
			up[i][u] = up[i - 1][up[i - 1][u]];
		for (Edge v : g[u])
			if (v.v != p)
			{
				dfs(v.v, u);
			}
		tout[u] = time++;
	}
	
	void dfs2(int u,int p,long d)
	{
		lz.updateUtil(1, tin[u], tout[u], d);
		mlz.updateUtil(1, tin[u], tout[u], d);

		for (Edge v : g[u])
			if (v.v != p)
			{
				dfs2(v.v, u, v.w);
			}
	}

	boolean isParent(int parent, int child) {
		return tin[parent] <= tin[child] && tout[child] <= tout[parent];
	}

	int lca(int a, int b) {
		if (isParent(a, b))
			return a;
		if (isParent(b, a))
			return b;
		for (int i = len - 1; i >= 0; i--)
			if (!isParent(up[i][a], b))
				a = up[i][a];
		return up[0][a];
	}

	void preprocess(int n, int root) {

		len = 1;
		while ((1 << len) <= n)
			++len;
		up = new int[len][n];
		tin = new int[n];
		tout = new int[n];
		dfs(root, root);
	}
	
    class Edge
	{
    	int u;
		int v;
		long w;
		Edge(int b,int a,long c)
		{
			u=b;
			v=a;
			w=c;
		}
	}
    
    class MinLazyPropagation {
		long tree[];
		long lazy[];
		int n;

		public MinLazyPropagation(int n) {
			tree = new long[4*n];
			lazy = new long[4*n];
			this.n=n;
		}
		
		void print(int node,int start,int end)
		{
			if (lazy[node] != 0) {
				tree[node] += lazy[node];
				if (start != end) {
					lazy[2 * node] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				lazy[node] = 0;
			}
			
			if (start > end || start > n-1 || end < 0)
				return;
			tr(start+" "+end+" "+tree[node]);
			if (start!=end)
			{
				int mid=(start+end)>>1;
				print(2*node,start,mid);
				print(2*node+1,mid+1,end);
			}
		}

		
		void updateUtil(int node,int l,int r,long val)
		{
			
			updateRange(node, 0,n-1, l, r, val);
			
		}
		
		long queryUtil(int node,int l,int r)
		{
			
			return queryRange(node,0,n-1, l, r);
		}

		void updateRange(int node, int start, int end, int l, int r, long val) {
			if (lazy[node] != 0) {
				tree[node] += lazy[node];
				if (start != end) {
					lazy[2 * node] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				lazy[node] = 0;
			}
			if (start > end || start > r || end < l)
				return ;

			if (start >= l && end <= r) {
			
				tree[node] += val;
				if (start != end) {
					lazy[node * 2] += val;
					lazy[node * 2 + 1] += val;
				}
				return ;
			}
			int mid = (start + end) >> 1;
			updateRange(node * 2, start, mid, l, r, val);
			updateRange(node * 2 + 1, mid + 1, end, l, r, val);
			tree[node] = Math.min(tree[2*node],tree[2*node+1]);
		}

		long queryRange(int node, int start, int end, int l, int r) {
			
			if (start > r || end < l || start > end)
				return Integer.MAX_VALUE;
			
			if (lazy[node] != 0) {
				tree[node] += lazy[node];
				if (start != end) {
					lazy[2 * node] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				lazy[node] = 0;
			}

			if (start >= l && end <= r)
				return tree[node];

			int mid = (start + end) >> 1;
			return Math.min(queryRange(node * 2, start, mid, l, r) , queryRange(node * 2 + 1, mid + 1, end, l, r));
		}
	}
    
	class LazyPropagation {
		long tree[];
		long lazy[];
		int n;
		public LazyPropagation(int n) {
			tree = new long[4 * n];
			lazy = new long[4 * n];
			this.n=n;
		}

		void updateUtil(int node,int l,int r,long val)
		{
			updateRange(node, 0,n-1, l, r, val);
		}
		
		long queryUtil(int node,int l,int r)
		{
			return queryRange(node,0,n-1, l, r);
		}
		
		void updateRange(int node, int start, int end, int l, int r, long val) {
			if (lazy[node] != 0) {
				tree[node] += (end - start + 1) * lazy[node];
				if (start != end) {
					lazy[2 * node] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				lazy[node] = 0;
			}
			if (start > end || start > r || end < l)
				return;

			if (start >= l && end <= r) {
				tree[node] += (end - start + 1) * val;
				if (start != end) {
					lazy[node * 2] += val;
					lazy[node * 2 + 1] += val;
				}
				return;
			}
			int mid = (start + end) >> 1;
			updateRange(node * 2, start, mid, l, r, val);
			updateRange(node * 2 + 1, mid + 1, end, l, r, val);
			tree[node] = tree[node * 2] + tree[node * 2 + 1];

		}

		long queryRange(int node, int start, int end, int l, int r) {
			if (start > r || end < l || start > end)
				return 0;
			if (lazy[node] != 0) {
				tree[node] += (end - start + 1) * lazy[node];
				if (start != end) {
					lazy[2 * node] += lazy[node];
					lazy[node * 2 + 1] += lazy[node];
				}
				lazy[node] = 0;
			}

			if (start >= l && end <= r)
				return tree[node];

			int mid = (start + end) >> 1;
			return queryRange(node * 2, start, mid, l, r) + queryRange(node * 2 + 1, mid + 1, end, l, r);
		}
	}
	
	
	void run() throws Exception {
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}
	public static void main(String[] args) throws Exception {
		new IndiaHacks().run();
	}
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = in.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() {
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(b))
			;
		return b;
	}
	
	private double nd() {
		return Double.parseDouble(ns());
	}
	
	private char nc() {
		return (char) skip();
	}
	
	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(inSpaceChar(b))) { // when nextLine, (inSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(inSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	
	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	
	private boolean oj = true;
	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
	
}