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 = 200010;
const long long inf = 66666666666666666ll;
struct node {
  long long d1, d2, d, lazy;
  node() {
    d1 = d2 = d = inf;
    lazy = 0;
  }
  node(long long x, long long y) {
    d1 = x, d2 = y, d = x + y;
    lazy = 0;
  }
} tr[maxn << 2];
struct edge {
  int v, w, num;
};
vector<edge> e[maxn];
int n, m, bel[maxn << 1];
int cnt, pos[maxn], dfn[maxn], top[maxn];
int to[maxn], dis[maxn], st[maxn], en[maxn], val[maxn], fro[maxn];
long long d[maxn];
void dfs(const int &u, const int &fa) {
  st[u] = ++cnt, dfn[cnt] = u;
  for (int v, i = 0; i < e[u].size(); i++) {
    v = e[u][i].v;
    if (v == fa) continue;
    d[v] = d[u] + (val[v] = e[u][i].w), bel[e[u][i].num] = u, dfs(v, u);
  }
  en[u] = cnt;
}
node min(const node &a, const node &b) { return a.d < b.d ? a : b; }
void pushup(int o) {
  if (tr[(o << 1)].d < tr[(o << 1 | 1)].d)
    tr[o].d = tr[(o << 1)].d, tr[o].d1 = tr[(o << 1)].d1,
    tr[o].d2 = tr[(o << 1)].d2;
  else
    tr[o].d = tr[(o << 1 | 1)].d, tr[o].d1 = tr[(o << 1 | 1)].d1,
    tr[o].d2 = tr[(o << 1 | 1)].d2;
}
void pushdown(int o) {
  tr[(o << 1)].lazy += tr[o].lazy;
  tr[(o << 1 | 1)].lazy += tr[o].lazy;
  tr[(o << 1)].d1 += tr[o].lazy;
  tr[(o << 1 | 1)].d1 += tr[o].lazy;
  tr[(o << 1)].d += tr[o].lazy;
  tr[(o << 1 | 1)].d += tr[o].lazy;
  tr[o].lazy = 0;
}
void build(int o, int l, int r) {
  if (l == r) {
    tr[o] = node(d[dfn[r]], dis[dfn[r]]);
    return;
  }
  int mid = (l + r) >> 1;
  build((o << 1), l, mid);
  build((o << 1 | 1), mid + 1, r);
  pushup(o);
}
void add(int o, int l, int r, int s, int t, int w) {
  if (s <= l && r <= t) {
    tr[o].lazy += w;
    tr[o].d1 += w;
    tr[o].d += w;
    return;
  }
  if (tr[o].lazy) pushdown(o);
  int mid = (l + r) >> 1;
  if (s <= mid) add((o << 1), l, mid, s, t, w);
  if (mid < t) add((o << 1 | 1), mid + 1, r, s, t, w);
  pushup(o);
}
void change(int o, int l, int r, int s, int w) {
  if (s == l && s == r) {
    tr[o].d2 = w;
    tr[o].d = tr[o].d1 + w;
    return;
  }
  if (tr[o].lazy) pushdown(o);
  int mid = (l + r) >> 1;
  if (s <= mid)
    change((o << 1), l, mid, s, w);
  else
    change((o << 1 | 1), mid + 1, r, s, w);
  pushup(o);
}
node askmin(int o, int l, int r, int s, int t) {
  if (s <= l && r <= t) return tr[o];
  if (tr[o].lazy) pushdown(o);
  int mid = (l + r) >> 1;
  node res;
  if (s <= mid) res = min(res, askmin((o << 1), l, mid, s, t));
  if (mid < t) res = min(res, askmin((o << 1 | 1), mid + 1, r, s, t));
  pushup(o);
  return res;
}
long long askdis(int o, int l, int r, int s) {
  if (s == l && r == s) return tr[o].d1;
  if (tr[o].lazy) pushdown(o);
  int mid = (l + r) >> 1;
  long long res;
  if (s <= mid)
    res = askdis((o << 1), l, mid, s);
  else
    res = askdis((o << 1 | 1), mid + 1, r, s);
  pushup(o);
  return res;
}
int main() {
  node tmp1, tmp2;
  long long ans, dis1, dis2;
  int u, v, w, M = 1;
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    e[u].push_back((edge){v, w, i});
    to[i] = v;
  }
  for (int i = 1; i < n; i++) {
    cin >> u >> v;
    cin >> dis[u];
    fro[i - 1] = u;
  }
  dfs(1, 1), build(1, 1, n);
  while (m--) {
    cin >> w >> u >> v;
    if (w == 1) {
      if (u < n)
        add(1, 1, n, st[to[u]], en[to[u]], v - val[to[u]]), val[to[u]] = v;
      else
        change(1, 1, n, st[fro[u - n]], v);
    } else {
      tmp1 = askmin(1, 1, n, st[u], en[u]);
      dis1 = askdis(1, 1, n, st[u]);
      dis2 = askdis(1, 1, n, st[v]);
      ans = tmp1.d - dis1 + dis2;
      if (st[v] >= st[u] && st[v] <= en[u]) ans = min(ans, dis2 - dis1);
      cout << ans << '\n';
    }
  }
  return 0;
}