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;
char buf[1 << 21], *p1 = buf, *p2 = buf;
namespace wode {
template <typename T>
inline void read(T &x) {
  static char ch;
  bool f = 1;
  for (x = 0,
      ch = (p1 == p2 &&
                    (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
                ? EOF
                : *p1++);
       !isdigit(ch);
       ch = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
                 ? EOF
                 : *p1++))
    if (ch == '-') f = 0;
  for (; isdigit(ch);
       x = (x << 1) + (x << 3) + (ch ^ 48),
       ch = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
                 ? EOF
                 : *p1++))
    ;
  x = f ? x : -x;
}
template <typename T>
inline void print(T x, char ch = 0) {
  if (!x) {
    putchar(48);
    if (ch) putchar(ch);
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  static int Stack[sizeof(T) * 3], top = -1;
  for (; x; Stack[++top] = x % 10, x /= 10)
    ;
  for (; ~top; putchar(Stack[top--] + 48))
    ;
  if (ch) putchar(ch);
}
template <typename T>
inline T max(T x, T y) {
  return x < y ? y : x;
}
template <typename T>
inline T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
inline void chkmax(T &x, T y) {
  x = x < y ? y : x;
}
template <typename T>
inline void chkmin(T &x, T y) {
  x = x < y ? x : y;
}
}  // namespace wode
using wode::chkmax;
using wode::chkmin;
using wode::print;
using wode::read;
int n, m, ver[200001], nxt[200001], head[200001], edge[200001], id[200001],
    fan[200001], ans, bian[400001], deep, len[200001], f[200001], x, y, z,
    ad[800001], b[200001], id1;
long long d[200001], dat[800001];
void dfs(int x, int fa) {
  id[x] = ++deep, len[x] = 1, f[x] = fa, fan[deep] = x;
  for (register int i = head[x]; i; i = nxt[i])
    d[ver[i]] = d[x] + (long long)edge[i], dfs(ver[i], x),
    len[x] += len[ver[i]];
}
void build(int q, int l, int r) {
  if (l == r) {
    dat[q] = d[fan[l]] + b[fan[l]];
    return;
  }
  int mid = l + r >> 1;
  build(q << 1, l, mid), build(q << 1 | 1, mid + 1, r);
  dat[q] = dat[q << 1] < dat[q << 1 | 1] ? dat[q << 1] : dat[q << 1 | 1];
}
inline void spread(int q, int l, int r, int mid) {
  if (ad[q]) {
    ad[q << 1] += ad[q], ad[q << 1 | 1] += ad[q];
    dat[q << 1] += ad[q], dat[q << 1 | 1] += ad[q];
    ad[q] = 0;
  }
}
void change(int q, int l1, int r1, int l, int r, int k) {
  if (l <= l1 && r1 <= r) {
    dat[q] += k, ad[q] += k;
    return;
  }
  int mid = l1 + r1 >> 1;
  spread(q, l1, r1, mid);
  if (l <= mid) change(q << 1, l1, mid, l, r, k);
  if (r > mid) change(q << 1 | 1, mid + 1, r1, l, r, k);
  dat[q] = dat[q << 1] < dat[q << 1 | 1] ? dat[q << 1] : dat[q << 1 | 1];
}
long long ask(int q, int l1, int r1, int l, int r) {
  if (l <= l1 && r1 <= r) return dat[q];
  int mid = l1 + r1 >> 1;
  spread(q, l1, r1, mid);
  long long tot = 1e18;
  if (l <= mid) chkmin(tot, ask(q << 1, l1, mid, l, r));
  if (r > mid) chkmin(tot, ask(q << 1 | 1, mid + 1, r1, l, r));
  return tot;
}
long long askp(int q, int l1, int r1, int point) {
  if (l1 == r1) return dat[q];
  int mid = l1 + r1 >> 1;
  spread(q, l1, r1, mid);
  if (point <= mid)
    return askp(q << 1, l1, mid, point);
  else
    return askp(q << 1 | 1, mid + 1, r1, point);
}
inline void add(int x, int y, int z) {
  ver[++ans] = y, edge[ans] = z, nxt[ans] = head[x], head[x] = ans;
}
int main() {
  read(n), read(m);
  for (register int i = 1; i < n; ++i) read(x), read(y), read(z), add(x, y, z);
  dfs(1, 0);
  for (register int i = n; i <= n - 1 << 1; ++i)
    read(x), read(y), read(z), b[x] = z, bian[i] = x;
  build(1, 1, n);
  while (m--) {
    read(id1), read(x), read(y);
    if (id1 == 1) {
      if (x < n) {
        int u = ver[x];
        change(1, 1, n, id[u], id[u] + len[u] - 1, y - edge[x]), edge[x] = y;
      } else
        change(1, 1, n, id[bian[x]], id[bian[x]], y - b[bian[x]]),
            b[bian[x]] = y;
    } else if (id[y] >= id[x] && id[y] <= id[x] + len[x] - 1)
      print(askp(1, 1, n, id[y]) - b[y] - askp(1, 1, n, id[x]) + b[x], '\n');
    else
      print(askp(1, 1, n, id[y]) - b[y] - askp(1, 1, n, id[x]) + b[x] +
                ask(1, 1, n, id[x], id[x] + len[x] - 1),
            '\n');
  }
  return 0;
}