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 size1 = 8e5;
const long long INF = 1e18;
const int INF1 = 1e9;
const double eps = 1e-5;
const long long mod = 1e9 + 7;
vector<vector<int> > graph(size1);
vector<vector<long long> > graph1(size1);
static int maxder[size1], minder[size1], d[size1], v[size1], u[size1], w[size1],
    tin[size1], tout[size1];
static bool used[size1];
static long long ras[size1];
static long long tree[size1], tree1[size1], tree2[size1], tree3[size1],
    w1[size1];
int num = 1;
int time1 = 0;
void dfs(int v) {
  used[v] = true;
  minder[v] = INF1;
  for (int i = 0; i < graph[v].size(); i++) {
    if (!used[graph[v][i]]) {
      dfs(graph[v][i]);
      minder[v] = min(minder[v], minder[graph[v][i]]);
    }
  }
  maxder[v] = num;
  num++;
  minder[v] = min(minder[v], maxder[v]);
}
void dfs1(int v, long long ras1, int depth) {
  time1++;
  used[v] = true;
  ras[maxder[v]] = ras1;
  d[v] = depth;
  tin[v] = time1;
  for (int i = 0; i < graph[v].size(); i++) {
    if (!used[graph[v][i]]) {
      dfs1(graph[v][i], ras1 + graph1[v][i], depth + 1);
    }
  }
  time1++;
  tout[v] = time1;
}
void build_tree(int tl, int tr, int pos) {
  if (tl == tr) {
    tree[pos] = ras[tl];
  } else {
    int tm = (tl + tr) / 2;
    build_tree(tl, tm, pos * 2);
    build_tree(tm + 1, tr, pos * 2 + 1);
    tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
  }
}
void prib(int tl, int tr, int pos, int l, int r, long long x) {
  if (l <= tl && tr <= r) {
    tree1[pos] += x;
  } else {
    int tm = (tl + tr) / 2;
    if (max(tl, l) <= min(tm, r)) {
      prib(tl, tm, pos * 2, l, r, x);
    }
    if (max(tm + 1, l) <= min(tr, r)) {
      prib(tm + 1, tr, pos * 2 + 1, l, r, x);
    }
    tree[pos] = tree[pos * 2] + tree[pos * 2 + 1] +
                tree1[pos * 2] * (tm - tl + 1) + tree1[pos * 2 + 1] * (tr - tm);
  }
}
long long zn(int tl, int tr, int pos, int pos1, long long add) {
  if (tl == pos1 && tr == pos1) {
    return add + tree[pos] + tree1[pos];
  } else {
    int tm = (tl + tr) / 2;
    if (tl <= pos1 && pos1 <= tm) {
      return zn(tl, tm, pos * 2, pos1, add + tree1[pos]);
    } else {
      return zn(tm + 1, tr, pos * 2 + 1, pos1, add + tree1[pos]);
    }
  }
}
void build_tree1(int tl, int tr, int pos) {
  if (tl == tr) {
    tree2[pos] = ras[tl] + w1[tl];
  } else {
    int tm = (tl + tr) / 2;
    build_tree1(tl, tm, pos * 2);
    build_tree1(tm + 1, tr, pos * 2 + 1);
    tree2[pos] = min(tree2[pos * 2], tree2[pos * 2 + 1]);
  }
}
void upd2(int tl, int tr, int pos, int l, int r, long long x) {
  if (l <= tl && tr <= r) {
    tree3[pos] += x;
  } else {
    int tm = (tl + tr) / 2;
    if (max(tl, l) <= min(tm, r)) {
      upd2(tl, tm, pos * 2, l, r, x);
    }
    if (max(tm + 1, l) <= min(tr, r)) {
      upd2(tm + 1, tr, pos * 2 + 1, l, r, x);
    }
    tree2[pos] = min(tree2[pos * 2] + tree3[pos * 2],
                     tree2[pos * 2 + 1] + tree3[pos * 2 + 1]);
  }
}
long long zn1(int tl, int tr, int pos, int l, int r, long long add) {
  if (l <= tl && tr <= r) {
    return add + tree3[pos] + tree2[pos];
  } else {
    int tm = (tl + tr) / 2;
    long long ans = INF;
    if (max(l, tl) <= min(r, tm)) {
      ans = min(ans, zn1(tl, tm, pos * 2, l, r, add + tree3[pos]));
    }
    if (max(tm + 1, l) <= min(tr, r)) {
      ans = min(ans, zn1(tm + 1, tr, pos * 2 + 1, l, r, add + tree3[pos]));
    }
    return ans;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q, i;
  cin >> n >> q;
  for (i = 1; i <= n - 1; i++) {
    cin >> v[i] >> u[i] >> w[i];
    graph[v[i]].push_back(u[i]);
    graph[u[i]].push_back(v[i]);
    graph1[v[i]].push_back(w[i]);
    graph1[u[i]].push_back(w[i]);
  }
  dfs(1);
  for (i = n; i <= 2 * n - 2; i++) {
    cin >> v[i] >> u[i] >> w[i];
    w1[maxder[v[i]]] = w[i];
  }
  memset(used, false, sizeof used);
  dfs1(1, 0, 0);
  build_tree(1, n, 1);
  build_tree1(1, n, 1);
  for (i = 1; i <= q; i++) {
    int t, a, b;
    cin >> t >> a >> b;
    if (t == 1) {
      if (a >= n) {
        upd2(1, n, 1, maxder[v[a]], maxder[v[a]], b - w1[maxder[v[a]]]);
        w1[maxder[v[a]]] = b;
      } else {
        int v1 = 0;
        if (d[v[a]] > d[u[a]]) {
          v1 = v[a];
        } else {
          v1 = u[a];
        }
        prib(1, n, 1, minder[v1], maxder[v1], b - w[a]);
        upd2(1, n, 1, minder[v1], maxder[v1], b - w[a]);
        w[a] = b;
      }
    } else {
      long long res = INF;
      if (max(tin[a], tin[b]) <= min(tout[a], tout[b]) && d[a] <= d[b]) {
        res = min(res, zn(1, n, 1, maxder[b], 0) - zn(1, n, 1, maxder[a], 0));
      }
      res = min(res, zn1(1, n, 1, minder[a], maxder[a], 0) -
                         zn(1, n, 1, maxder[a], 0) + zn(1, n, 1, maxder[b], 0));
      cout << res << endl;
    }
  }
  return 0;
}