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>
using namespace std;
int n, q;
struct edge {
  int from;
  int to;
  int len;
  int next;
  edge() {}
  edge(int u, int v, int w, int nex) {
    from = u;
    to = v;
    len = w;
  }
};
edge E[200005 * 2];
int head[200005];
edge G[200005 * 2];
int size = 0;
void add_edge(int u, int v, int w) {
  size++;
  E[size].from = u;
  E[size].to = v;
  E[size].len = w;
  E[size].next = head[u];
  head[u] = size;
}
int deep[200005];
long long dist[200005];
int to_root[200005];
int cnt = 0;
int l[200005], r[200005];
void dfs(int x, int fa) {
  l[x] = ++cnt;
  for (int i = head[x]; i; i = E[i].next) {
    int y = E[i].to;
    if (y != fa) {
      deep[y] = deep[x] + 1;
      dist[y] = dist[x] + (long long)E[i].len;
      dfs(y, x);
    }
  }
  r[x] = cnt;
}
struct segment_tree {
  struct node {
    int l;
    int r;
    long long v;
    long long mark;
    int len() { return r - l + 1; }
  } tree[200005 << 2];
  segment_tree() { memset(tree, 0, sizeof(tree)); }
  void push_up(int pos) {
    tree[pos].v = min(tree[pos << 1].v, tree[pos << 1 | 1].v);
  }
  void build(int l, int r, int pos) {
    tree[pos].l = l;
    tree[pos].r = r;
    tree[pos].mark = tree[pos].v = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, pos << 1);
    build(mid + 1, r, pos << 1 | 1);
  }
  void push_down(int pos) {
    if (tree[pos].mark) {
      tree[pos << 1].mark += tree[pos].mark;
      tree[pos << 1].v += tree[pos].mark;
      tree[pos << 1 | 1].mark += tree[pos].mark;
      tree[pos << 1 | 1].v += tree[pos].mark;
      tree[pos].mark = 0;
    }
  }
  void update(int L, int R, long long v, int pos) {
    if (L <= tree[pos].l && R >= tree[pos].r) {
      tree[pos].v += v;
      tree[pos].mark += v;
      return;
    }
    push_down(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if (L <= mid) update(L, R, v, pos << 1);
    if (R > mid) update(L, R, v, pos << 1 | 1);
    push_up(pos);
  }
  long long query(int L, int R, int pos) {
    if (L <= tree[pos].l && R >= tree[pos].r) {
      return tree[pos].v;
    }
    push_down(pos);
    long long ans = 0x7fffffffffffffff;
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if (L <= mid) ans = min(ans, query(L, R, pos << 1));
    if (R > mid) ans = min(ans, query(L, R, pos << 1 | 1));
    return ans;
  }
};
segment_tree T1, T2;
int main() {
  int u, v, w, cmd, id;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d %d %d", &u, &v, &w);
    add_edge(u, v, w);
    add_edge(v, u, w);
  }
  deep[1] = 1;
  dfs(1, 0);
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d %d %d", &u, &v, &w);
    G[i] = edge(u, v, w, -1);
    to_root[u] = w;
  }
  T1.build(1, n, 1);
  T2.build(1, n, 1);
  for (int i = 1; i <= n; i++) {
    T1.update(l[i], l[i], dist[i], 1);
    T2.update(l[i], l[i], dist[i] + to_root[i], 1);
  }
  int x, y;
  long long ans;
  for (int i = 1; i <= q; i++) {
    scanf("%d", &cmd);
    if (cmd == 1) {
      scanf("%d %d", &id, &w);
      if (id <= n - 1) {
        x = E[id * 2 - 1].from;
        y = E[id * 2 - 1].to;
        if (deep[x] > deep[y]) swap(x, y);
        T1.update(l[y], r[y], w - E[id * 2 - 1].len, 1);
        T2.update(l[y], r[y], w - E[id * 2 - 1].len, 1);
        E[id * 2 - 1].len = w;
      } else {
        x = G[id - (n - 1)].from;
        y = G[id - (n - 1)].to;
        if (deep[x] > deep[y]) swap(x, y);
        T2.update(l[y], l[y], w - G[id - (n - 1)].len, 1);
        G[id - (n - 1)].len = w;
      }
    } else {
      scanf("%d %d", &u, &v);
      if ((l[u] <= l[v] && r[u] >= r[v])) {
        printf("%I64d\n", T1.query(l[v], r[v], 1) - T1.query(l[u], r[u], 1));
      } else {
        ans = T2.query(l[u], r[u], 1) - T1.query(l[u], l[u], 1) +
              T1.query(l[v], l[v], 1);
        printf("%I64d\n", ans);
      }
    }
  }
}