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;
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  if (p1 == p2) {
    p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);
    if (p1 == p2) return EOF;
  }
  return *p1++;
}
inline void Read(int& x) {
  char c = nc();
  for (; c < '0' || c > '9'; c = nc())
    ;
  for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - 48, c = nc())
    ;
}
struct Edge {
  int f, t, nx, w;
} e[200010 << 1];
long long c[200010 << 2], p[200010 << 2], Pa[200010], c2[200010 << 2];
int d[200010], Top[200010], Son[200010], l[200010], r[200010], s[200010],
    f[200010], w[200010], x, y, z;
int h[200010], Num;
int i, j, k, n, m, Q, a[200010], L;
inline void Dfs1(int x, int y) {
  d[x] = ++y;
  l[x] = ++Num;
  s[x] = 1;
  w[Num] = x;
  for (int i = h[x]; i; i = e[i].nx) {
    Pa[e[i].t] = Pa[x] + e[i].w;
    Dfs1(e[i].t, y);
    s[x] += s[e[i].t];
    if (s[e[i].t] > s[Son[x]]) Son[x] = e[i].t;
  }
  r[x] = Num;
}
inline void Dfs2(int x, int y) {
  Top[x] = y;
  if (Son[x]) Dfs2(Son[x], y);
  for (int i = h[x]; i; i = e[i].nx)
    if (e[i].t != Son[x]) Dfs2(e[i].t, e[i].t);
}
inline long long Min(long long x, long long y) { return x < y ? x : y; }
inline void Up(int x) { c[x] = Min(c[x << 1], c[x << 1 | 1]); }
inline void Down(int x) {
  if (p[x]) {
    c[x << 1] += p[x];
    c2[x << 1] += p[x];
    p[x << 1] += p[x];
    c[x << 1 | 1] += p[x];
    c2[x << 1 | 1] += p[x];
    p[x << 1 | 1] += p[x];
    p[x] = 0;
  }
}
inline void Update1(int x, int l, int r, int y, int z) {
  if (l == r) {
    c[x] += z;
    return;
  }
  Down(x);
  int Mid = l + r >> 1;
  if (y <= Mid)
    Update1(x << 1, l, Mid, y, z);
  else
    Update1(x << 1 | 1, Mid + 1, r, y, z);
  Up(x);
}
inline void Update2(int x, int l, int r, int L, int R, int y) {
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    c[x] += y;
    c2[x] += y;
    p[x] += y;
    return;
  }
  Down(x);
  int Mid = l + r >> 1;
  Update2(x << 1, l, Mid, L, R, y);
  Update2(x << 1 | 1, Mid + 1, r, L, R, y);
  Up(x);
}
inline long long Query(int x, int l, int r, int L, int R) {
  if (l > R || r < L) return 1e18;
  if (l >= L && r <= R) return c[x];
  Down(x);
  int Mid = l + r >> 1;
  return Min(Query(x << 1, l, Mid, L, R), Query(x << 1 | 1, Mid + 1, r, L, R));
}
inline long long Query2(int x, int l, int r, int y) {
  if (l == r) return c2[x];
  Down(x);
  int Mid = l + r >> 1;
  if (y <= Mid) return Query2(x << 1, l, Mid, y);
  return Query2(x << 1 | 1, Mid + 1, r, y);
}
inline void Build(int x, int l, int r) {
  if (l == r) {
    c[x] = Pa[w[l]] + a[w[l]];
    c2[x] = Pa[w[l]];
    return;
  }
  int Mid = l + r >> 1;
  Build(x << 1, l, Mid);
  Build(x << 1 | 1, Mid + 1, r);
  Up(x);
}
inline int Lca(int x, int y) {
  while (Top[x] != Top[y])
    if (d[Top[x]] > d[Top[y]])
      x = f[Top[x]];
    else
      y = f[Top[y]];
  return d[x] > d[y] ? y : x;
}
int main() {
  Read(n);
  Read(Q);
  for (i = 1; i < n; i++)
    Read(e[i].f), Read(e[i].t), Read(e[i].w), e[i].nx = h[e[i].f],
                                              h[e[i].f] = i, f[e[i].t] = e[i].f;
  for (i = 1; i < n; i++)
    Read(e[i + n - 1].f), Read(e[i + n - 1].t), Read(a[e[i + n - 1].f]);
  Num = 0;
  Dfs1(1, 0);
  Dfs2(1, 1);
  Build(1, 1, n);
  while (Q--) {
    Read(k);
    Read(x);
    Read(y);
    if (k == 1) {
      if (x >= n)
        Update1(1, 1, n, l[e[x].f], y - a[e[x].f]), a[e[x].f] = y;
      else
        Update2(1, 1, n, l[e[x].t], r[e[x].t], y - e[x].w), e[x].w = y;
    } else {
      L = Lca(x, y);
      if (L == x)
        printf("%I64d\n", Query2(1, 1, n, l[y]) - Query2(1, 1, n, l[x]));
      else
        printf("%I64d\n", Query(1, 1, n, l[x], r[x]) - Query2(1, 1, n, l[x]) +
                              Query2(1, 1, n, l[y]));
    }
  }
  return 0;
}