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;
long long n, m, tin[400005], in, ty, lv[400005], ind, dist1, dist2, d[400005],
    lazy1[2000005], lazy2[2000005], out[400005], tree1[2000005], tree2[2000005],
    a, b, c, v1, v2, s[400005], mp[400005];
pair<long long, long long> idx[400005];
vector<pair<long long, long long> > v[400005];
map<long long, long long> mp1;
void dfs(int a, int p, int w) {
  in++;
  tin[a] = in;
  mp1[in] = a;
  lv[a] = lv[p] + 1;
  d[a] = d[p] + w;
  for (int i = 0; i < v[a].size(); i++) {
    dfs(v[a][i].first, a, v[a][i].second);
  }
  out[a] = in;
}
void update1(long long node, long long start, long long end, long long l,
             long long r, long long val) {
  if (l > r) return;
  if (l == start && r == end) {
    tree1[node] += val;
    lazy1[node] += val;
  } else {
    tree1[node * 2] += lazy1[node];
    tree1[node * 2 + 1] += lazy1[node];
    lazy1[node * 2] += lazy1[node];
    lazy1[node * 2 + 1] += lazy1[node];
    lazy1[node] = 0;
    long long mid = (start + end) / 2;
    update1(node * 2, start, mid, l, min(r, mid), val);
    update1(node * 2 + 1, mid + 1, end, max(l, mid + 1), r, val);
    tree1[node] = min(tree1[node * 2], tree1[node * 2 + 1]);
  }
}
long long get_ans1(long long node, long long start, long long end, long long l,
                   long long r) {
  if (l > r) return 1e14;
  if (l == start && r == end) {
    return tree1[node];
  } else {
    tree1[node * 2] += lazy1[node];
    tree1[node * 2 + 1] += lazy1[node];
    lazy1[node * 2] += lazy1[node];
    lazy1[node * 2 + 1] += lazy1[node];
    lazy1[node] = 0;
    long long mid = (start + end) / 2;
    long long p1 = get_ans1(node * 2, start, mid, l, min(r, mid));
    long long p2 = get_ans1(node * 2 + 1, mid + 1, end, max(l, mid + 1), r);
    return min(p1, p2);
  }
}
void update2(long long node, long long start, long long end, long long l,
             long long r, long long val) {
  if (l > r) return;
  if (l == start && r == end) {
    tree2[node] += val;
    lazy2[node] += val;
  } else {
    tree2[node * 2] += lazy2[node];
    tree2[node * 2 + 1] += lazy2[node];
    lazy2[node * 2] += lazy2[node];
    lazy2[node * 2 + 1] += lazy2[node];
    lazy2[node] = 0;
    long long mid = (start + end) / 2;
    update2(node * 2, start, mid, l, min(r, mid), val);
    update2(node * 2 + 1, mid + 1, end, max(l, mid + 1), r, val);
    tree2[node] = min(tree2[node * 2], tree2[node * 2 + 1]);
  }
}
long long get_ans2(long long node, long long start, long long end, long long l,
                   long long r) {
  if (l > r) return 1e14;
  if (l == start && r == end) {
    return tree2[node];
  } else {
    tree2[node * 2] += lazy2[node];
    tree2[node * 2 + 1] += lazy2[node];
    lazy2[node * 2] += lazy2[node];
    lazy2[node * 2 + 1] += lazy2[node];
    lazy2[node] = 0;
    long long mid = (start + end) / 2;
    long long p1 = get_ans2(node * 2, start, mid, l, min(r, mid));
    long long p2 = get_ans2(node * 2 + 1, mid + 1, end, max(l, mid + 1), r);
    return min(p1, p2);
  }
}
int main() {
  std::ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n - 1; i++) {
    cin >> a >> b >> c;
    idx[i] = {a, b};
    s[i] = c;
    v[a].push_back({b, c});
  }
  dfs(1, 0, 0);
  for (int i = n; i <= 2 * n - 2; i++) {
    cin >> a >> b >> c;
    idx[i] = {a, b};
    mp[a] = c;
    v[a].push_back({b, c});
  }
  for (int i = 1; i <= n; i++) {
    update1(1, 1, n, tin[i], tin[i], d[i]);
    update2(1, 1, n, tin[i], tin[i], d[i] + mp[i]);
  }
  for (int i = 1; i <= m; i++) {
    cin >> ty >> ind >> c;
    if (ty == 1) {
      if (ind >= n) {
        a = idx[ind].first;
        b = idx[ind].second;
        update2(1, 1, n, tin[a], tin[a], c - mp[a]);
        mp[a] = c;
      } else {
        a = idx[ind].first;
        b = idx[ind].second;
        update1(1, 1, n, tin[b], out[b], c - s[ind]);
        update2(1, 1, n, tin[b], out[b], c - s[ind]);
        s[ind] = c;
      }
    } else {
      a = ind;
      b = c;
      if (tin[a] <= tin[b] && out[a] >= out[b]) {
        dist1 = get_ans1(1, 1, n, tin[a], tin[a]);
        dist2 = get_ans1(1, 1, n, tin[b], tin[b]);
        cout << dist2 - dist1 << endl;
        continue;
      }
      dist1 = get_ans1(1, 1, n, tin[a], tin[a]);
      dist2 = get_ans2(1, 1, n, tin[a], out[a]);
      cout << dist2 - dist1 + get_ans1(1, 1, n, tin[b], tin[b]) << endl;
    }
  }
}