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 maxn = 2e5 + 20;
vector<vector<pair<int, int>>> G(maxn);
pair<pair<int, int>, int> p[maxn];
int in[maxn], out[maxn], tot, id[maxn], dep[maxn], fa[maxn][21];
long long sum[maxn << 2], lazy[maxn << 2], Min[maxn << 2], dis[maxn], to[maxn];
inline void maintain(int rt) {
  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  Min[rt] = min(Min[rt << 1], Min[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
  if (l == r) {
    Min[rt] = to[l] + dis[l];
    sum[rt] = to[l];
    return;
  }
  int mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  maintain(rt);
}
inline void pushdown(int rt) {
  if (lazy[rt]) {
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    sum[rt << 1] += lazy[rt], sum[rt << 1 | 1] += lazy[rt];
    Min[rt << 1] += lazy[rt], Min[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;
  }
}
void update(int l, int r, int v, int L, int R, int rt) {
  if (l <= L && r >= R) {
    sum[rt] += v;
    lazy[rt] += v;
    Min[rt] += v;
    return;
  }
  pushdown(rt);
  int mid = L + R >> 1;
  if (l <= mid) update(l, r, v, L, mid, rt << 1);
  if (r > mid) update(l, r, v, mid + 1, R, rt << 1 | 1);
  maintain(rt);
}
void update(int q, int v, int L, int R, int rt) {
  if (L == R) {
    Min[rt] += v;
    return;
  }
  pushdown(rt);
  int mid = L + R >> 1;
  if (q <= mid)
    update(q, v, L, mid, rt << 1);
  else
    update(q, v, mid + 1, R, rt << 1 | 1);
  maintain(rt);
}
long long query(int l, int r, int L, int R, int rt) {
  if (l <= L && r >= R) {
    return Min[rt];
  }
  pushdown(rt);
  int mid = L + R >> 1;
  long long ans = 1e18;
  if (l <= mid) ans = min(ans, query(l, r, L, mid, rt << 1));
  if (r > mid) ans = min(ans, query(l, r, mid + 1, R, rt << 1 | 1));
  return ans;
}
long long query(int q, int L, int R, int rt) {
  if (L == R) {
    return sum[rt];
  }
  pushdown(rt);
  int mid = L + R >> 1;
  long long ans = 0;
  if (q <= mid)
    ans += query(q, L, mid, rt << 1);
  else
    ans += query(q, mid + 1, R, rt << 1 | 1);
  return ans;
}
void dfs(int u, int f) {
  in[u] = ++tot;
  fa[u][0] = f;
  dep[u] = dep[f] + 1;
  for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (auto p : G[u]) {
    int v = p.first;
    if (v == f) continue;
    to[v] = to[u] + p.second;
    dfs(v, u);
  }
  out[u] = tot;
}
int Lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 0; i <= 20; i++)
    if ((dep[x] - dep[y]) & (1 << i)) x = fa[x][i];
  if (x == y) return x;
  for (int i = 20; i >= 0; i--)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
int main(void) {
  int n, q, a, b, c;
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    scanf("%d %d %d", &a, &b, &c);
    G[a].push_back(make_pair(b, c));
    p[i] = pair<pair<int, int>, int>(make_pair(a, b), c);
  }
  for (int i = 1; i < n; i++) {
    scanf("%d %d %d", &a, &b, &c);
    id[i] = a;
    dis[a] = c;
  }
  dfs(1, 0);
  for (int i = 1; i < n; i++) {
    update(in[p[i].first.second], out[p[i].first.second], p[i].second, 1, n, 1);
    update(in[i + 1], dis[i + 1], 1, n, 1);
  }
  while (q--) {
    scanf("%d %d %d", &a, &b, &c);
    if (a == 1) {
      if (b < n) {
        update(in[p[b].first.second], out[p[b].first.second], c - p[b].second,
               1, n, 1),
            p[b].second = c;
      } else
        update(in[id[b - n + 1]], c - dis[id[b - n + 1]], 1, n, 1),
            dis[id[b - n + 1]] = c;
    } else {
      if (Lca(b, c) != b)
        printf("%lld\n", query(in[c], 1, n, 1) - query(in[b], 1, n, 1) +
                             query(in[b], out[b], 1, n, 1));
      else
        printf("%lld\n", query(in[c], 1, n, 1) - query(in[b], 1, n, 1));
    }
  }
  return 0;
}