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 CPP):

Solution:
#include <bits/stdc++.h>
struct sgt {
  struct node {
    int l, r, ls, rs, tag, sum, mini;
  };
  int n, cnt;
  std::vector<node> a;

 private:
  int make() {
    a.push_back(node{0, 0, 0, 0, 0, 0});
    ++cnt;
    return cnt;
  }
  void put(int k, int v) {
    int l = a[k].l, r = a[k].r;
    a[k].tag = a[k].tag + v;
    a[k].mini = a[k].mini + v;
    a[k].sum = a[k].sum + (r - l + 1) * v;
  }
  void pushdown(int k) {
    int tag = a[k].tag, ls = a[k].ls, rs = a[k].rs;
    if (!tag) return;
    put(ls, tag);
    put(rs, tag);
    a[k].tag = 0;
    return;
  }
  void pushup(int k) {
    int ls = a[k].ls, rs = a[k].rs;
    a[k].mini = std::min(a[ls].mini, a[rs].mini);
    a[k].sum = a[ls].sum + a[rs].sum;
  }
  void build(int k, int x, int y) {
    a[k].l = x, a[k].r = y;
    if (x == y) return;
    int mid = (x + y) / 2, num;
    num = make();
    a[k].ls = num;
    build(a[k].ls, x, mid);
    num = make();
    a[k].rs = num;
    build(a[k].rs, mid + 1, y);
  }
  void add(int k, int x, int y, int v) {
    int l = a[k].l, r = a[k].r, ls = a[k].ls, rs = a[k].rs;
    if (x <= l && r <= y) {
      put(k, v);
      return;
    }
    pushdown(k);
    int mid = (l + r) / 2;
    if (x <= mid) add(ls, x, y, v);
    if (mid < y) add(rs, x, y, v);
    pushup(k);
  }
  int qmin(int k, int x, int y) {
    int l = a[k].l, r = a[k].r, ls = a[k].ls, rs = a[k].rs;
    if (x <= l && r <= y) return a[k].mini;
    pushdown(k);
    int mid = (l + r) / 2, ans = 1000000000;
    if (x <= mid) ans = std::min(ans, qmin(ls, x, y));
    if (mid < y) ans = std::min(ans, qmin(rs, x, y));
    return ans;
  }
  int qsum(int k, int x, int y) {
    int l = a[k].l, r = a[k].r, ls = a[k].ls, rs = a[k].rs;
    if (x <= l && r <= y) return a[k].sum;
    pushdown(k);
    int mid = (l + r) / 2, ans = 0;
    if (x <= mid) ans = ans + qsum(ls, x, y);
    if (mid < y) ans = ans + qsum(rs, x, y);
    return ans;
  }

 public:
  void pre(int x) {
    a.clear();
    cnt = -1;
    n = x;
    make();
    make();
    build(1, 1, n);
  }
  void add1(int x, int v) { add(1, x, x, v); }
  void add2(int x, int y, int v) { add(1, x, y, v); }
  int qmin1(int x) { return qmin(1, x, x); }
  int qmin2(int x, int y) { return qmin(1, x, y); }
  int qsum1(int x) { return qsum(1, x, x); }
  int qsum2(int x, int y) { return qsum(1, x, y); }
  void clear() { a.clear(); }
};
struct edge {
  int to, val;
};
sgt sgt1, sgt2;
std::vector<edge> a[200005];
int n, q, now = 0, x[400005], y[400005], val[400005], f[200005], g[200005],
          id[200005], dep[200005], sz[200005], l[200005], r[200005];
void add(int x, int y, int v) {
  a[x].push_back(edge{y, v});
  a[y].push_back(edge{x, v});
}
void dfs(int v, int d, int fa) {
  id[v] = ++now;
  dep[v] = d;
  sz[v] = 1;
  for (int i = 0; i < a[v].size(); i++) {
    int u = a[v][i].to;
    if (u == fa) continue;
    dfs(u, d + 1, v);
    sz[v] = sz[v] + sz[u];
  }
  l[v] = id[v], r[v] = id[v] + sz[v] - 1;
}
void solve(int v, int d, int fa) {
  f[v] = d;
  g[v] = f[v] + g[v];
  for (int i = 0; i < a[v].size(); i++) {
    int u = a[v][i].to;
    if (u == fa) continue;
    solve(u, d + a[v][i].val, v);
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= 2 * n - 2; i++) scanf("%d%d%d", &x[i], &y[i], &val[i]);
  for (int i = 1; i <= n - 1; i++) add(x[i], y[i], val[i]);
  for (int i = n; i <= 2 * n - 2; i++) g[x[i]] = val[i];
  now = 0;
  dfs(1, 1, -1);
  solve(1, 0, -1);
  sgt1.pre(n), sgt2.pre(n);
  for (int i = 1; i <= n; i++) sgt1.add1(id[i], f[i]), sgt2.add1(id[i], g[i]);
  while (q--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int xx, k;
      scanf("%d%d", &xx, &k);
      int p = dep[x[xx]] > dep[y[xx]] ? x[xx] : y[xx];
      if (xx <= n - 1) {
        sgt1.add2(l[p], r[p], k - val[xx]);
        sgt2.add2(l[p], r[p], k - val[xx]);
        val[xx] = k;
      } else {
        sgt2.add1(id[p], k - val[xx]);
        val[xx] = k;
      }
    } else if (opt == 2) {
      int xx, yy, ans = 0;
      scanf("%d%d", &xx, &yy);
      if (l[xx] <= l[yy] && r[yy] <= r[xx]) {
        ans = sgt1.qsum1(id[yy]) - sgt1.qsum1(id[xx]);
      } else {
        ans =
            sgt2.qmin2(l[xx], r[xx]) - sgt1.qsum1(id[xx]) + sgt1.qsum1(id[yy]);
      }
      printf("%d\n", ans);
    }
  }
  sgt1.clear(), sgt2.clear();
  return 0;
}