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 io {
  char r[15500000], w[2600010];
  int nr, nw, q[20], t;
  io() { r[fread(r, 1, 15500000, stdin)] = 0; }
  inline int read() {
    int x = 0;
    for (; r[nr] < 48; ++nr)
      ;
    for (; r[nr] > 47; ++nr) x = (x << 1) + (x << 3) + r[nr] - 48;
    return x;
  }
  inline void write(long long x) {
    if (!x) w[nw++] = 48;
    for (; x; x /= 10) q[++t] = x % 10;
    for (; t; --t) w[nw++] = q[t] + 48;
    w[nw++] = '\n';
  }
  ~io() { fwrite(w, 1, nw, stdout); }
} io;
int n, q, st[200005], pv[200005], p1[200005], pw[200005], tot;
struct edge {
  int u, v, w;
} e[200005 << 1];
inline void side(int u, int v, int w) {
  pv[++tot] = v;
  pw[tot] = w;
  p1[tot] = st[u];
  st[u] = tot;
}
int bg[200005], ed[200005], id[200005], dfn;
long long d[200005];
int d2[200005];
inline void dfs(int x) {
  bg[x] = ++dfn;
  id[dfn] = x;
  for (int i = st[x]; i; i = p1[i]) {
    d[pv[i]] = d[x] + pw[i];
    dfs(pv[i]);
  }
  ed[x] = dfn;
}
struct node {
  int l, r;
  long long d, mn;
} t[200005 << 2];
inline long long min(long long a, long long b) { return a < b ? a : b; }
inline void upd(int x) { t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn); }
inline void push_down(int x) {
  if (t[x].d) {
    int l = x << 1, r = l | 1, d = t[x].d;
    t[l].d += d;
    t[l].mn += d;
    t[r].d += d;
    t[r].mn += d;
    t[x].d = 0;
  }
}
inline void build(int x, int l, int r) {
  t[x].l = l;
  t[x].r = r;
  if (l == r) {
    t[x].d = d[id[l]];
    t[x].mn = t[x].d + d2[id[l]];
    return;
  }
  int m = l + r >> 1;
  build(x << 1, l, m);
  build(x << 1 | 1, m + 1, r);
  upd(x);
}
inline void init() {
  n = io.read();
  q = io.read();
  for (int i = 1; i < n; ++i) {
    int u = io.read(), v = io.read(), w = io.read();
    e[i] = (edge){u, v, w};
    side(u, v, w);
  }
  for (int i = 1; i < n; ++i) {
    int u = io.read(), v = io.read(), w = io.read();
    e[n - 1 + i] = (edge){u, v, w};
    d2[u] = w;
  }
  dfs(1);
  build(1, 1, n);
}
inline long long query(int c, int x) {
  if (t[c].l == t[c].r) return t[c].d;
  push_down(c);
  int m = t[c].l + t[c].r >> 1;
  return query(x <= m ? c << 1 : c << 1 | 1, x);
}
inline long long query(int c, int l, int r) {
  if (l <= t[c].l && t[c].r <= r) return t[c].mn;
  push_down(c);
  int m = t[c].l + t[c].r >> 1;
  long long ret = 0x7fffffffffffffffll;
  if (l <= m) ret = query(c << 1, l, r);
  if (r > m) ret = min(ret, query(c << 1 | 1, l, r));
  return ret;
}
inline void inc(int c, int x, int d) {
  if (t[c].l == t[c].r) {
    t[c].mn += d;
    return;
  }
  push_down(c);
  int m = t[c].l + t[c].r >> 1;
  inc(x <= m ? c << 1 : c << 1 | 1, x, d);
  upd(c);
}
inline void inc(int c, int l, int r, int d) {
  if (l <= t[c].l && t[c].r <= r) {
    t[c].d += d;
    t[c].mn += d;
    return;
  }
  push_down(c);
  int m = t[c].l + t[c].r >> 1;
  if (l <= m) inc(c << 1, l, r, d);
  if (r > m) inc(c << 1 | 1, l, r, d);
  upd(c);
}
inline void solve() {
  while (q--) {
    int op = io.read(), x = io.read(), y = io.read();
    if (op == 2) {
      if (bg[x] <= bg[y] && bg[y] <= ed[x])
        io.write(query(1, bg[y]) - query(1, bg[x]));
      else
        io.write(query(1, bg[y]) - query(1, bg[x]) + query(1, bg[x], ed[x]));
    } else {
      int u = e[x].u, v = e[x].v, d = y - e[x].w;
      if (x < n)
        inc(1, bg[v], ed[v], d);
      else
        inc(1, bg[u], d);
      e[x].w = y;
    }
  }
}
int main() {
  init();
  solve();
  return 0;
}