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 = 5e5 + 20, maxm = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
const double PI = acos(-1.0);
int casn, n, m, k, nume;
int u[maxn], v[maxn], nx[maxn], head[maxn];
long long w[maxn];
void add(int a, int b, int c) {
  v[++nume] = b;
  nx[nume] = head[a], w[nume] = c;
  u[nume] = a;
  head[a] = nume;
}
int dfn, in[maxn], reid[maxn], out[maxn];
long long to1[maxn], dis[maxn];
void dfs(int now, long long s) {
  in[now] = ++dfn;
  reid[dfn] = now;
  for (int i = head[now]; i; i = nx[i])
    if (v[i] != 1) dfs(v[i], s + w[i]);
  out[now] = dfn, dis[now] = s + to1[now];
}
long long mn[maxn << 2 | 1], f[maxn << 2 | 1];
void down(int now) {
  if (f[now]) {
    mn[now << 1] += f[now];
    mn[now << 1 | 1] += f[now];
    f[now << 1] += f[now];
    f[now << 1 | 1] += f[now];
    f[now] = 0;
  }
}
void maketree(int s, int t, int now = 1) {
  mn[now] = dis[reid[s]];
  if (s == t) return;
  maketree(s, (s + t) / 2, now << 1);
  maketree((s + t) / 2 + 1, t, now << 1 | 1);
  mn[now] = min(mn[now << 1], mn[now << 1 | 1]);
}
void update(int s, int t, long long x, int l, int r, int now = 1) {
  if (s <= l && t >= r) {
    mn[now] += x, f[now] += x;
    return;
  }
  down(now);
  if (s <= (l + r) / 2) update(s, t, x, l, (l + r) / 2, now << 1);
  if (t > (l + r) / 2) update(s, t, x, (l + r) / 2 + 1, r, now << 1 | 1);
  mn[now] = min(mn[now << 1], mn[now << 1 | 1]);
}
long long query(int s, int t, int l, int r, int now = 1) {
  if (s <= l && t >= r) return mn[now];
  down(now);
  long long ret = 1e18;
  if (s <= (l + r) / 2) ret = query(s, t, l, (l + r) / 2, now << 1);
  if (t > (l + r) / 2)
    ret = min(query(s, t, (l + r) / 2 + 1, r, now << 1 | 1), ret);
  return ret;
}
int intree(int a, int b) { return in[b] <= in[a] && out[b] >= out[a]; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n - 1; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
  }
  for (int i = 1; i <= n - 1; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
    to1[a] = c;
  }
  dfs(1, 0);
  maketree(1, n, 1);
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == 1) {
      if (b <= n - 1) {
        update(in[v[b]], out[v[b]], c - w[b], 1, n);
        w[b] = c;
      } else {
        update(in[u[b]], in[u[b]], c - to1[u[b]], 1, n);
        to1[u[b]] = c;
      }
    } else {
      if (intree(c, b)) {
        cout << query(in[c], in[c], 1, n) - query(in[b], in[b], 1, n) - to1[c] +
                    to1[b]
             << '\n';
      } else {
        cout << query(in[b], out[b], 1, n) + query(in[c], in[c], 1, n) -
                    to1[c] - query(in[b], in[b], 1, n) + to1[b]
             << '\n';
      }
    }
  }
  return 0;
}