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;
const int N = 200005;
int n, q;
int cnte;
int head[N];
int nxt[N << 1], to[N << 1], val[N << 1];
inline void addedge(int x, int y, int v) {
  ++cnte;
  nxt[cnte] = head[x];
  to[cnte] = y, val[cnte] = v;
  head[x] = cnte;
}
int tort[N];
long long dis[N];
int tot;
int id[N];
int L[N], R[N];
int size[N], fa[N];
int dep[N], hson[N];
void dfs(int x) {
  L[x] = ++tot;
  id[tot] = x;
  size[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int nx = to[i];
    fa[nx] = x;
    dis[nx] = dis[x] + val[i];
    dep[nx] = dep[x] + 1;
    dfs(nx);
    size[x] += size[nx];
    if (size[nx] > size[hson[x]]) hson[x] = nx;
  }
  R[x] = tot;
}
int top[N];
void dfs2(int x, int tp) {
  top[x] = tp;
  if (hson[x]) {
    dfs2(hson[x], tp);
    for (int i = head[x]; i; i = nxt[i]) {
      int nx = to[i];
      if (nx == fa[x] || nx == hson[x]) continue;
      dfs2(nx, nx);
    }
  }
}
int LCA(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]])
      x = fa[top[x]];
    else
      y = fa[top[y]];
  }
  return dep[x] > dep[y] ? y : x;
}
long long mi[N << 2];
long long add[N << 2];
void up(int p) { mi[p] = min(mi[p << 1], mi[p << 1 | 1]); }
void down(int p) {
  if (add[p]) {
    long long &t = add[p];
    add[p << 1] += t, add[p << 1 | 1] += t;
    mi[p << 1] += t, mi[p << 1 | 1] += t;
    t = 0;
  }
}
void build(int l, int r, int p) {
  if (l == r) {
    mi[p] = dis[id[l]] + tort[id[l]];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
  up(p);
}
void update(int l, int r, int v, int p, int L = 1, int R = n) {
  if (l == L && r == R) {
    mi[p] += v;
    add[p] += v;
    return;
  }
  down(p);
  int mid = (L + R) >> 1;
  if (r <= mid)
    update(l, r, v, p << 1, L, mid);
  else if (l > mid)
    update(l, r, v, p << 1 | 1, mid + 1, R);
  else
    update(l, mid, v, p << 1, L, mid),
        update(mid + 1, r, v, p << 1 | 1, mid + 1, R);
  up(p);
}
long long query(int l, int r, int p, int L = 1, int R = n) {
  if (l == L && r == R) return mi[p];
  down(p);
  int mid = (L + R) >> 1;
  if (r <= mid)
    return query(l, r, p << 1, L, mid);
  else if (l > mid)
    return query(l, r, p << 1 | 1, mid + 1, R);
  return min(query(l, mid, p << 1, L, mid),
             query(mid + 1, r, p << 1 | 1, mid + 1, R));
}
struct edge {
  int a, b;
  int v;
} e[N << 1];
int cc;
void solve() {
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    addedge(a, b, c);
    e[++cc] = (edge){a, b, c};
  }
  for (int i = 1; i < n; ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    tort[a] = c;
    e[++cc] = (edge){a, b, c};
  }
  dfs(1);
  dfs2(1, 1);
  build(1, n, 1);
  while (q--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int i, w;
      scanf("%d %d", &i, &w);
      if (i >= n) {
        update(L[e[i].a], L[e[i].a], w - tort[e[i].a], 1);
        tort[e[i].a] = w;
        e[i].v = w;
      } else {
        update(L[e[i].b], R[e[i].b], w - e[i].v, 1);
        e[i].v = w;
      }
    } else {
      int x, y;
      scanf("%d %d", &x, &y);
      if (LCA(x, y) == x)
        printf("%lld\n",
               query(L[y], L[y], 1) - tort[y] - query(L[x], L[x], 1) + tort[x]);
      else
        printf("%lld\n", query(L[x], R[x], 1) -
                             (query(L[x], L[x], 1) - tort[x]) +
                             query(L[y], L[y], 1) - tort[y]);
    }
  }
}
int main() {
  solve();
  return 0;
}