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;
vector<pair<int, int>> g[200004];
multiset<int> ms[200004];
int eul[200004 << 1], lev[200004 << 1], h[200004], spt[20][200004 << 1],
    cid[200004], scnt, cpar[200004], cpos[200004], el[200004 << 1][3],
    lvl[200004], mnc[200004], lg[200004 << 1], dp[200004];
class segtree {
 private:
  int qx, qy;
  long long qz;
  vector<long long> lz;
  void build(int p, int l, int r) {
    if (l == r)
      st[p] = a[l];
    else {
      int m = (l + r) >> 1, p2 = p << 1;
      build(p2, l, m);
      build(p2 + 1, m + 1, r);
      st[p] = min(st[p2], st[p2 + 1]);
    }
  }
  long long rmq(int p, int l, int r) {
    if (qx <= l && r <= qy) return st[p];
    int m = (l + r) >> 1, p2 = p << 1;
    if (l != r && lz[p] != 0) {
      lz[p2] += lz[p];
      lz[p2 + 1] += lz[p];
      st[p2] += lz[p];
      st[p2 + 1] += lz[p];
      lz[p] = 0;
    }
    long long s = LLONG_MAX;
    if (qx <= m) s = rmq(p2, l, m);
    if (qy > m) s = min(s, rmq(p2 + 1, m + 1, r));
    return s;
  }
  void upd(int p, int l, int r) {
    if (qx <= l && r <= qy) {
      st[p] += qz;
      lz[p] += qz;
    } else {
      int m = (l + r) >> 1, p2 = p << 1;
      if (l != r && lz[p] != 0) {
        lz[p2] += lz[p];
        lz[p2 + 1] += lz[p];
        st[p2] += lz[p];
        st[p2 + 1] += lz[p];
        lz[p] = 0;
      }
      if (qx <= m) upd(p2, l, m);
      if (qy > m) upd(p2 + 1, m + 1, r);
      st[p] = min(st[p2], st[p2 + 1]);
    }
  }

 public:
  vector<long long> a, st;
  vector<int> ex;
  int len;
  void init() {
    int i;
    len = a.size();
    for (i = 1; i < len; ++i) a[i] += a[i - 1];
    for (i = 0; i < len; ++i) a[i] += *ms[ex[i]].begin();
    st.assign(len << 2, 0);
    lz.assign(len << 2, 0);
    build(1, 0, --len);
    a.clear();
    ex.clear();
  }
  long long rmqit(int l, int r) {
    if (l > r) return LLONG_MAX;
    qx = l;
    qy = r;
    return rmq(1, 0, len);
  }
  void updit(int l, int r, long long v) {
    qx = l;
    qy = r;
    qz = v;
    upd(1, 0, len);
  }
} sgts[200004];
class fenwick {
 private:
  vector<long long> ft;

 public:
  vector<int> a;
  int len;
  long long rsq(int b) {
    long long r = 0;
    for (++b; b; b -= (b & (-b))) r += ft[b];
    return r;
  }
  long long rsq(int l, int b) {
    if (l > b) return 0;
    if (l) return rsq(b) - rsq(l - 1);
    return rsq(b);
  }
  void upd(int i, int v) {
    for (++i; i <= len; i += (i & (-i))) ft[i] += v;
  }
  void init() {
    len = a.size();
    ft.assign(len + 1, 0);
    for (int i = 0; i < len; ++i) upd(i, a[i]);
    a.clear();
  }
} ft[200004];
int dfs(int x) {
  eul[++scnt] = x;
  lev[scnt] = lvl[x];
  spt[0][scnt] = scnt;
  h[x] = scnt;
  int y = -1, z, r = 0;
  for (auto& p : g[x]) {
    lvl[p.first] = lvl[x] + 1;
    dp[p.first] = x;
    z = dfs(p.first);
    if (z > y) {
      y = z;
      mnc[x] = p.first;
    }
    r += z;
    eul[++scnt] = x;
    lev[scnt] = lvl[x];
    spt[0][scnt] = scnt;
  }
  if (y == -1) mnc[x] = -1;
  return r + 1;
}
void buildhld(int x, int chain) {
  if (mnc[x] == -1) return;
  for (auto& p : g[x]) {
    if (p.first == mnc[x]) {
      cpos[p.first] = sgts[chain].a.size();
      cid[p.first] = chain;
      sgts[chain].a.push_back(p.second);
      sgts[chain].ex.push_back(p.first);
      ft[chain].a.push_back(p.second);
      buildhld(p.first, chain);
    } else {
      cpos[p.first] = 0;
      cid[p.first] = ++scnt;
      cpar[scnt] = p.first;
      sgts[scnt].a.push_back(p.second);
      sgts[scnt].ex.push_back(p.first);
      ft[scnt].a.push_back(p.second);
      buildhld(p.first, scnt);
      sgts[cid[p.first]].init();
      ft[cid[p.first]].init();
      if (sgts[cid[p.first]].st[1] <= 1000000)
        ms[x].insert(sgts[cid[p.first]].st[1]);
    }
  }
}
long long getSPbw2(int j, int k) {
  int x = cid[j], y = cid[k];
  long long z = 0;
  while (y != x) {
    z += ft[y].rsq(cpos[k]);
    k = dp[cpar[y]];
    y = cid[k];
  }
  return z + ft[y].rsq(cpos[j] + 1, cpos[k]);
}
long long getSPto1(int i) {
  int x = cid[i];
  return sgts[x].rmqit(cpos[i], sgts[x].len) - ft[x].rsq(cpos[i]);
}
inline int inp() {
  register unsigned int n = 0;
  register unsigned int c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') {
    n = (n << 3) + (n << 1) + c - '0';
    c = getchar();
  }
  return n;
}
inline void oup(unsigned long long int x) {
  unsigned char s[20];
  int i = 0;
  do {
    s[i++] = x % 10 + '0';
    x /= 10;
  } while (x);
  --i;
  while (i >= 0) {
    putchar(s[i--]);
  }
  putchar('\n');
}
int main() {
  int n, q, i, j, k, x, y, ii;
  multiset<int>::iterator it;
  long long zz, xx;
  n = inp();
  q = inp();
  j = 0;
  for (i = 1; i < n; ++i) {
    ++j;
    el[j][0] = inp();
    el[j][1] = inp();
    el[j][2] = inp();
    g[el[j][0]].emplace_back(el[j][1], el[j][2]);
  }
  ms[1].insert(0);
  for (i = 1; i < n; ++i) {
    ++j;
    el[j][0] = inp();
    el[j][1] = inp();
    el[j][2] = inp();
    ms[el[j][0]].insert(el[j][2]);
  }
  scnt = -1;
  dfs(1);
  x = scnt;
  for (j = 1; (1 << j) <= x; ++j)
    for (i = 0; i + (1 << j) <= x; ++i) {
      if (lev[spt[j - 1][i]] <= lev[spt[j - 1][i + (1 << (j - 1))]])
        spt[j][i] = spt[j - 1][i];
      else
        spt[j][i] = spt[j - 1][i + (1 << (j - 1))];
    }
  y = 1;
  j = 0;
  for (i = 1; i <= x; ++i) {
    if ((y << 1) <= i) {
      y <<= 1;
      ++j;
    }
    lg[i] = j;
  }
  cid[0] = scnt = cpar[0] = cpos[0] = 0;
  sgts[0].a.push_back(0);
  sgts[0].ex.push_back(1);
  ft[0].a.push_back(0);
  buildhld(1, 0);
  sgts[0].init();
  ft[0].init();
  while (q--) {
    cin >> i >> j >> k;
    if (i == 1) {
      if (el[j][1] == 1) {
        y = el[j][0];
        xx = *ms[y].begin();
        ms[y].erase(ms[y].lower_bound(el[j][2]));
        ms[y].insert(k);
        el[j][2] = k;
        if (xx != *ms[y].begin()) {
          x = cid[y];
          zz = sgts[x].st[1];
          sgts[x].updit(cpos[y], cpos[y], *ms[y].begin() - xx);
        } else
          continue;
      } else {
        x = cid[el[j][1]];
        zz = sgts[x].st[1];
        sgts[x].updit(cpos[el[j][1]], sgts[x].len, k - el[j][2]);
        ft[x].upd(cpos[el[j][1]], k - el[j][2]);
        el[j][2] = k;
      }
      while (x) {
        y = dp[cpar[x]];
        xx = *ms[y].begin();
        if (zz <= 1000000) {
          it = ms[y].lower_bound(zz);
          if (it != ms[y].end() && *it == zz) ms[y].erase(it);
        }
        if (sgts[x].st[1] <= 1000000) ms[y].insert(sgts[x].st[1]);
        if (xx != *ms[y].begin()) {
          x = cid[y];
          zz = sgts[x].st[1];
          sgts[x].updit(cpos[y], cpos[y], *ms[y].begin() - xx);
        } else
          break;
      }
    } else {
      y = j;
      ii = k;
      if (h[j] > h[k]) swap(j, k);
      x = lg[h[k] - h[j] + 1];
      if (lev[spt[x][h[j]]] <= lev[spt[x][h[k] - (1 << x) + 1]])
        x = eul[spt[x][h[j]]];
      else
        x = eul[spt[x][h[k] - (1 << x) + 1]];
      if (x == y)
        oup(getSPbw2(j, k));
      else
        oup(getSPto1(y) + getSPbw2(1, ii));
    }
  }
  return 0;
}