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 = 200100;
vector<pair<int, long long>> gr[MAXN];
long long curForwEdge[MAXN * 2], curBackEdge[MAXN * 2];
int n, q;
int tin[MAXN], tout[MAXN];
int edgeFrom[MAXN * 2], edgeTo[MAXN * 2];
long long costFromRoot[MAXN];
long long costToRoot[MAXN];
long long edgeFromVertexToRoot[MAXN];
struct SegmentTree {
  long long vals[4 * MAXN];
  long long additions[4 * MAXN];
  SegmentTree() {
    memset(vals, 0, sizeof(vals));
    memset(additions, 0, sizeof(additions));
  }
  void recalc(int v) { vals[v] = min(getV(2 * v + 1), getV(2 * v + 2)); }
  void push(int v) {
    additions[2 * v + 1] += additions[v];
    additions[2 * v + 2] += additions[v];
    additions[v] = 0;
  }
  void build(int v, int l, int r, long long* arr) {
    if (l == r) {
      vals[v] = arr[l];
      return;
    }
    int med = (l + r) / 2;
    build(2 * v + 1, l, med, arr);
    build(2 * v + 2, med + 1, r, arr);
    recalc(v);
  }
  long long getV(int v) { return additions[v] + vals[v]; }
  long long getMin(int v, int l, int r, int st, int fin) {
    if (l == st && r == fin) {
      return getV(v);
    }
    push(v);
    int med = (l + r) / 2;
    if (fin <= med) {
      long long res = getMin(2 * v + 1, l, med, st, fin);
      recalc(v);
      return res;
    }
    if (st > med) {
      long long res = getMin(2 * v + 2, med + 1, r, st, fin);
      recalc(v);
      return res;
    }
    long long lmin = getMin(2 * v + 1, l, med, st, med);
    long long rmin = getMin(2 * v + 2, med + 1, r, med + 1, fin);
    recalc(v);
    return min(lmin, rmin);
  }
  void addSeg(int v, int l, int r, int st, int fin, long long add) {
    if (l == st && r == fin) {
      additions[v] += add;
      return;
    }
    push(v);
    int med = (l + r) / 2;
    if (fin <= med) {
      addSeg(2 * v + 1, l, med, st, fin, add);
      recalc(v);
      return;
    }
    if (st > med) {
      addSeg(2 * v + 2, med + 1, r, st, fin, add);
      recalc(v);
      return;
    }
    addSeg(2 * v + 1, l, med, st, med, add),
        addSeg(2 * v + 2, med + 1, r, med + 1, fin, add);
    recalc(v);
  }
};
int tmm = 0;
void dfs(int v, long long pref) {
  tmm++;
  tin[v] = tmm;
  costFromRoot[tmm] = pref;
  int edgeToLook = edgeFromVertexToRoot[v];
  costToRoot[tmm] = pref + curBackEdge[edgeToLook];
  for (pair<int, long long> to : gr[v]) {
    dfs(to.first, pref + to.second);
  }
  tout[v] = tmm;
}
SegmentTree fromRoot;
SegmentTree toRoot;
void minDist() {
  int u, v;
  scanf("%d%d", &u, &v);
  int whu = tin[u];
  int whv = tin[v];
  if (tin[v] >= tin[u] && tout[v] <= tout[u]) {
    long long costU = fromRoot.getMin(0, 1, n, whu, whu);
    long long costV = fromRoot.getMin(0, 1, n, whv, whv);
    printf("%lld\n", costV - costU);
  } else {
    long long costU = fromRoot.getMin(0, 1, n, whu, whu);
    long long bestUnderU = toRoot.getMin(0, 1, n, tin[u], tout[u]);
    long long costV = fromRoot.getMin(0, 1, n, whv, whv);
    long long back = bestUnderU - costU;
    printf("%lld\n", back + costV);
  }
}
void changeEdge() {
  int edgeNum;
  int newVal;
  scanf("%d%d", &edgeNum, &newVal);
  if (edgeNum <= n - 1) {
    int delta = newVal - curForwEdge[edgeNum];
    curForwEdge[edgeNum] = newVal;
    int vertex = edgeTo[edgeNum];
    fromRoot.addSeg(0, 1, n, tin[vertex], tout[vertex], delta);
    toRoot.addSeg(0, 1, n, tin[vertex], tout[vertex], delta);
  } else {
    int delta = newVal - curBackEdge[edgeNum];
    curBackEdge[edgeNum] = newVal;
    int vertex = edgeFrom[edgeNum];
    toRoot.addSeg(0, 1, n, tin[vertex], tin[vertex], delta);
  }
}
void debug() {
  cerr << "debug" << endl;
  for (int i = 1; i <= n; i++) {
    int wh = tin[i];
    cerr << i << " " << fromRoot.getMin(0, 1, n, wh, wh) << " "
         << toRoot.getMin(0, 1, n, wh, wh) << " "
         << toRoot.getMin(0, 1, n, tin[i], tout[i]) << endl;
  }
  cerr << "end debug" << endl;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n - 1; i++) {
    int aa, bb, cc;
    scanf("%d%d%d", &aa, &bb, &cc);
    gr[aa].push_back({bb, cc});
    curForwEdge[i] = cc;
    edgeFrom[i] = aa;
    edgeTo[i] = bb;
  }
  for (int i = 1; i <= n - 1; i++) {
    int aa, bb, cc;
    scanf("%d%d%d", &aa, &bb, &cc);
    curBackEdge[i + n - 1] = cc;
    edgeFrom[i + n - 1] = aa;
    edgeTo[i + n - 1] = bb;
    edgeFromVertexToRoot[aa] = i + n - 1;
  }
  dfs(1, 0);
  fromRoot.build(0, 1, n, costFromRoot);
  toRoot.build(0, 1, n, costToRoot);
  for (int qi = 1; qi <= q; qi++) {
    int tp;
    scanf("%d", &tp);
    if (tp == 2) {
      minDist();
    } else {
      changeEdge();
    }
  }
  return 0;
}