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;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long n, m, tot, head[1000001], sz[1000001];
long long a[1000001], tcnt;
long long pre[1000001], b[1000001], dis[1000001], tpos[1000001];
struct edge {
  long long to, nxt, dis;
} g[1000001];
inline void made(long long from, long long to, long long dis) {
  g[++tot].to = to;
  g[tot].nxt = head[from];
  head[from] = tot;
  g[tot].dis = dis;
}
void dfs(long long u, long long faa) {
  sz[u] = 1;
  tpos[u] = ++tcnt;
  pre[tcnt] = u;
  for (long long i = head[u]; i; i = g[i].nxt) {
    long long v = g[i].to;
    if (v == faa) continue;
    dis[v] = dis[u] + g[i].dis;
    a[v] = g[i].dis;
    dfs(v, u);
    sz[u] += sz[v];
  }
}
long long seg[1000001], tag[1000001];
inline void pushup(long long rt) {
  seg[rt] = min(seg[rt << 1], seg[rt << 1 | 1]);
}
void build(long long rt, long long lb, long long rb) {
  if (lb == rb) return (void)(seg[rt] = b[pre[lb]] + dis[pre[lb]]);
  build(rt << 1 | 1, ((lb + rb) >> 1) + 1, rb);
  build(rt << 1, lb, ((lb + rb) >> 1));
  pushup(rt);
}
inline void pushdown(long long rt, long long lb, long long rb) {
  if (tag[rt]) {
    long long ls = rt << 1, rs = rt << 1 | 1;
    tag[ls] += tag[rt];
    tag[rs] += tag[rt];
    seg[ls] += tag[rt];
    seg[rs] += tag[rt];
    tag[rt] = 0;
  }
}
long long querymin(long long rt, long long lb, long long rb, long long l,
                   long long r) {
  if (lb > r || rb < l) return 999999999;
  if (lb >= l && rb <= r) return seg[rt];
  pushdown(rt, lb, rb);
  return min(querymin(rt << 1, lb, ((lb + rb) >> 1), l, r),
             querymin(rt << 1 | 1, ((lb + rb) >> 1) + 1, rb, l, r));
}
void update(long long rt, long long lb, long long rb, long long l, long long r,
            long long w) {
  if (lb > r || rb < l) return;
  if (lb >= l && rb <= r) return (void)(seg[rt] += w, tag[rt] += w);
  pushdown(rt, lb, rb);
  update(rt << 1, lb, ((lb + rb) >> 1), l, r, w);
  update(rt << 1 | 1, ((lb + rb) >> 1) + 1, rb, l, r, w);
  pushup(rt);
}
inline long long Get(long long x) {
  return querymin(1, 1, n, tpos[x], tpos[x]);
}
long long e[1000001];
signed main() {
  n = read(), m = read();
  for (long long i = 1; i < n; i++) {
    long long x = read(), y = read(), w = read();
    made(x, y, w);
  }
  for (long long i = n; i <= 2 * n - 2; i++) {
    long long x = read(), y = read(), w = read();
    b[x] = w;
    e[i] = x;
  }
  dfs(1, 0);
  build(1, 1, n);
  while (m--) {
    long long opt = read();
    if (opt == 1) {
      long long i = read(), w = read();
      if (i >= n) {
        long long v = e[i];
        update(1, 1, n, tpos[v], tpos[v], w - b[v]);
        b[v] = w;
      } else {
        long long v = g[i].to;
        update(1, 1, n, tpos[v], tpos[v] + sz[v] - 1, w - a[v]);
        a[v] = w;
      }
    } else {
      long long u = read(), v = read();
      if (tpos[u] <= tpos[v] && tpos[v] <= tpos[u] + sz[u] - 1) {
        printf("%lld\n", Get(v) - b[v] - Get(u) + b[u]);
        continue;
      }
      long long Ans = 0;
      Ans = querymin(1, 1, n, tpos[u], tpos[u] + sz[u] - 1) - (Get(u) - b[u]);
      Ans += Get(v) - b[v];
      printf("%lld\n", Ans);
    }
  }
  return 0;
}