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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.io.BufferedInputStream;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		BufferedInputStream in = new BufferedInputStream(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskB {
		int time = 0;

		public void solve(int testNumber, BufferedInputStream _in, PrintWriter out) {

			InputReader in = new InputReader(_in);
			long startTime = System.currentTimeMillis();
			int n = in.nextInt();
			int q = in.nextInt();
			int[] s = new int[2 * n - 2];
			int[] t = new int[2 * n - 2];
			int[] w = new int[2 * n - 2];

			for (int i = 0; i < 2 * n - 2; ++i) {
				s[i] = in.nextInt() - 1;
				t[i] = in.nextInt() - 1;
				w[i] = in.nextInt();
			}

			ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
			int[] edgeToParent = new int[n];
			for (int i = 0; i < n; ++i) adj.add(new ArrayList<>());
			for (int i = 0; i < n - 1; ++i) {
				adj.get(s[i]).add(t[i]);
				edgeToParent[t[i]] = w[i];
			}

			long[] toRoot = new long[n];
			long[] fromRoot = new long[n];

			for (int i = n - 1; i < 2 * n - 2; ++i) {
				toRoot[s[i]] = w[i];
			}

			int[] st = new int[n];
			int[] ft = new int[n];
			int[] id = new int[n];

			dfs(0, -1, st, ft, id, fromRoot, edgeToParent, adj);
			long[] mn = new long[n];
			long[] su = new long[n];
			for (int i = 0; i < n; ++i) {
				mn[st[i]] = fromRoot[i] + toRoot[i];
				su[st[i]] = fromRoot[i];
			}


			SegmentTreeMinQueryL minTree = new SegmentTreeMinQueryL(mn);
			SegmentTreeSumL sumTree = new SegmentTreeSumL(su);

			int type = 0;
			int u, v;
			int delta;

			for (int i = 0; i < q; ++i) {
				type = in.nextInt();
				if (type == 1) {
					u = in.nextInt() - 1;
					v = in.nextInt();
					delta = v - w[u];
					w[u] = v;
					if (t[u] == 0) {
						minTree.incRange(st[s[u]], st[s[u]], delta);
					} else {
						sumTree.incRange(st[t[u]], ft[t[u]], delta);
						minTree.incRange(st[t[u]], ft[t[u]], delta);
					}
				} else {
					u = in.nextInt() - 1;
					v = in.nextInt() - 1;
					if (st[u] <= st[v] && ft[v] <= ft[u]) {
						out.println(sumTree.querySum(st[v], st[v]) - sumTree.querySum(st[u], st[u]));
					} else {
						long tou = sumTree.querySum(st[u], st[u]);
						long tov = sumTree.querySum(st[v], st[v]);
						long minU = minTree.queryMin(st[u], ft[u]) - tou;
						out.println(tov + minU);
					}
				}
			}


			in.close();
			System.err.println("Time: " + (System.currentTimeMillis() - startTime) + " miliseconds");
		}

		private void dfs(int v, int par, int[] st, int[] ft, int[] id, long[] fromRoot, int[] edgeToParent, ArrayList<ArrayList<Integer>> adj) {
			st[v] = time;
			id[time] = v;
			time++;
			if (par != -1) {
				fromRoot[v] = fromRoot[par] + edgeToParent[v];
			}
			for (Integer u : adj.get(v)) {
				dfs(u, v, st, ft, id, fromRoot, edgeToParent, adj);
			}

			ft[v] = time - 1;
		}

	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public void close() {

		}

	}

	static class SegmentTreeSumL {
		SegmentTreeSumL.SegmentData[] data;
		int sz;

		private void initSize(int n) {
			for (sz = 1; sz < n; sz <<= 1) ;
			data = new SegmentTreeSumL.SegmentData[2 * sz];
		}

		public SegmentTreeSumL(int n) {
			initSize(n);
			initVal(1, 0, sz - 1, null);
		}

		public SegmentTreeSumL(long[] a) {
			initSize(a.length);
			initVal(1, 0, sz - 1, a);
		}

		private void initVal(int node, int b, int e, long[] a) {
			if (e > b) {
				initVal(node << 1, b, (b + e) >> 1, a);
				initVal((node << 1) + 1, ((b + e) >> 1) + 1, e, a);
				data[node] = new SegmentTreeSumL.SegmentData(b, e, 0, data[node << 1].sum + data[(node << 1) + 1].sum);

			} else {
				if (a != null)
					data[node] = new SegmentTreeSumL.SegmentData(b, e, 0, b >= a.length ? 0 : a[b]);
				else
					data[node] = new SegmentTreeSumL.SegmentData(b, e, 0, 0);
			}
		}

		private void lazyUpdate(int node, int b, int e) {


			int left = node << 1;
			int right = left + 1;
			long lz = data[node].lazySum;
			if (data[left].resetId < data[node].resetId) {
				data[left].resetId = data[node].resetId;
				data[left].resetVal = data[node].resetVal;
				data[left].sum = data[node].resetVal * (((e + b) >> 1) - b + 1);
				data[left].lazySum = lz;
			} else {
				data[left].lazySum += lz;
			}

			data[left].sum += lz * (((e + b) >> 1) - b + 1);


			if (data[right].resetId < data[node].resetId) {
				data[right].resetId = data[node].resetId;
				data[right].resetVal = data[node].resetVal;
				data[right].sum = data[node].resetVal * (e - ((e + b) >> 1));
				data[right].lazySum = lz;
			} else {
				data[right].lazySum += lz;
			}

			data[right].sum += lz * (e - ((e + b) >> 1));

			data[node].lazySum = 0;

		}

		private void _incRange(int node, int b, int e, int ii, int jj, long delta) {
			if (ii > e || jj < b) {
				return;
			}
			if (b >= ii && e <= jj) {
				data[node].lazySum += delta;
				data[node].sum += delta * (e - b + 1);
				return;
			}
			int left = node << 1;
			int right = left + 1;
			lazyUpdate(node, b, e);
			_incRange(left, b, (b + e) >> 1, ii, jj, delta);
			_incRange(right, ((b + e) >> 1) + 1, e, ii, jj, delta);
			data[node].sum = data[left].sum + data[right].sum;
		}

		public void incRange(int a, int b, long delta) {
			_incRange(1, 0, sz - 1, a, b, delta);
		}

		private long _querySum(int node, int b, int e, int ii, int jj) {
			if (ii > e || jj < b) {
				return 0;
			}
			if (b >= ii && e <= jj) {
				return data[node].sum;
			}
			int left = node << 1;
			int right = left + 1;
			lazyUpdate(node, b, e);
			long re = (_querySum(left, b, (b + e) >> 1, ii, jj) + _querySum(right, ((b + e) >> 1) + 1, e, ii, jj));
			//data[node].sum = (data[left].sum + data[right].sum);
			return re;
		}

		public long querySum(int a, int b) {
			return _querySum(1, 0, sz - 1, a, b);
		}

		private static class SegmentData {
			int a;
			int b;
			long lazySum;
			long sum;
			int resetId = 0;
			long resetVal = 0;

			public SegmentData(int a, int b, long lazySum, long sum) {
				this.a = a;
				this.b = b;
				this.lazySum = lazySum;
				this.sum = sum;
			}

		}

	}

	static class SegmentTreeMinQueryL {
		SegmentTreeMinQueryL.SegmentData[] data;
		int sz;

		private void initSize(int n) {
			for (sz = 1; sz < n; sz <<= 1) ;
			data = new SegmentTreeMinQueryL.SegmentData[2 * sz];
		}

		public SegmentTreeMinQueryL(int n) {
			initSize(n);
			initVal(1, 0, sz - 1, null);
		}

		public SegmentTreeMinQueryL(long[] a) {
			initSize(a.length);
			initVal(1, 0, sz - 1, a);
		}

		private void initVal(int node, int b, int e, long[] a) {
			if (e > b) {
				initVal(node << 1, b, (b + e) >> 1, a);
				initVal((node << 1) + 1, ((b + e) >> 1) + 1, e, a);
				data[node] = new SegmentTreeMinQueryL.SegmentData(b, e, 0, Math.min(data[node << 1].min, data[(node << 1) + 1].min));

			} else {
				if (a != null)
					data[node] = new SegmentTreeMinQueryL.SegmentData(b, e, 0, b >= a.length ? 0 : a[b]);
				else
					data[node] = new SegmentTreeMinQueryL.SegmentData(b, e, 0, 0);
			}
		}

		private void lazyUpdate(int node, int b, int e) {


			int left = node << 1;
			int right = left + 1;
			long lz = data[node].lazySum;
			if (data[left].resetId < data[node].resetId) {
				data[left].resetId = data[node].resetId;
				data[left].resetVal = data[node].resetVal;
				data[left].min = data[node].resetVal;
				data[left].lazySum = lz;
			} else {
				data[left].lazySum += lz;
			}

			data[left].min += lz;


			if (data[right].resetId < data[node].resetId) {
				data[right].resetId = data[node].resetId;
				data[right].resetVal = data[node].resetVal;
				data[right].min = data[node].resetVal;
				data[right].lazySum = lz;
			} else {
				data[right].lazySum += lz;
			}

			data[right].min += lz;

			data[node].lazySum = 0;

		}

		private void _incRange(int node, int b, int e, int ii, int jj, long delta) {
			if (ii > e || jj < b) {
				return;
			}
			if (b >= ii && e <= jj) {
				data[node].lazySum += delta;
				data[node].min += delta;
				return;
			}
			int left = node << 1;
			int right = left + 1;
			lazyUpdate(node, b, e);
			_incRange(left, b, (b + e) >> 1, ii, jj, delta);
			_incRange(right, ((b + e) >> 1) + 1, e, ii, jj, delta);
			data[node].min = Math.min(data[left].min, data[right].min);
		}

		public void incRange(int a, int b, long delta) {
			_incRange(1, 0, sz - 1, a, b, delta);
		}

		private long _queryMin(int node, int b, int e, int ii, int jj) {
			if (ii > e || jj < b) {
				return Long.MAX_VALUE;
			}
			if (b >= ii && e <= jj) {
				return data[node].min;
			}
			int left = node << 1;
			int right = left + 1;
			lazyUpdate(node, b, e);
			long re = Math.min(_queryMin(left, b, (b + e) >> 1, ii, jj), _queryMin(right, ((b + e) >> 1) + 1, e, ii, jj));
			//data[node].sum = (data[left].sum + data[right].sum);
			return re;
		}

		public long queryMin(int a, int b) {
			return _queryMin(1, 0, sz - 1, a, b);
		}

		private static class SegmentData {
			int a;
			int b;
			long lazySum;
			long min;
			int resetId = 0;
			long resetVal = 0;

			public SegmentData(int a, int b, long lazySum, long min) {
				this.a = a;
				this.b = b;
				this.lazySum = lazySum;
				this.min = min;
			}

		}

	}
}