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;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
int n, m, q;
vector<int> g[200001];
struct edge {
  int u, v;
  long long c;
} e[400001];
bool done[200001];
int l[200001];
int r[200001];
int cnt;
void dfs(int u) {
  done[u] = 1;
  l[u] = r[u] = ++cnt;
  for (int v : g[u]) dfs(v);
  r[u] = cnt;
}
const long long inf = 1LL << 55;
struct segment_tree {
  long long t[800001];
  long long lz[800001];
  void update(int i, int l, int r, int u, int v, long long x) {
    if (l > v || r < u) return;
    if (u <= l && v >= r) {
      t[i] += x;
      lz[i] += x;
    } else {
      int m = (l + r) / 2;
      t[2 * i] += lz[i];
      t[2 * i + 1] += lz[i];
      lz[2 * i] += lz[i];
      lz[2 * i + 1] += lz[i];
      lz[i] = 0;
      update(2 * i, l, m, u, v, x);
      update(2 * i + 1, m + 1, r, u, v, x);
      t[i] = min(t[2 * i], t[2 * i + 1]);
    }
  }
  long long get(int i, int l, int r, int u, int v) {
    if (l > v || r < u) return inf;
    if (u <= l && v >= r)
      return t[i];
    else {
      int m = (l + r) / 2;
      t[2 * i] += lz[i];
      t[2 * i + 1] += lz[i];
      lz[2 * i] += lz[i];
      lz[2 * i + 1] += lz[i];
      lz[i] = 0;
      return min(get(2 * i, l, m, u, v), get(2 * i + 1, m + 1, r, u, v));
    }
  }
  long long getelement(int i, int l, int r, int u) {
    if (l == r)
      return t[i];
    else {
      int m = (l + r) / 2;
      t[2 * i] += lz[i];
      t[2 * i + 1] += lz[i];
      lz[2 * i] += lz[i];
      lz[2 * i + 1] += lz[i];
      lz[i] = 0;
      if (m >= u)
        return getelement(2 * i, l, m, u);
      else
        return getelement(2 * i + 1, m + 1, r, u);
    }
  }
} dist, toroot;
int main() {
  read(n);
  read(q);
  m = 2 * n - 2;
  for (int i = 1; i <= m; i++) {
    read(e[i].u);
    read(e[i].v);
    read(e[i].c);
  }
  for (int i = 1; i < n; i++) g[e[i].u].push_back(e[i].v);
  dfs(1);
  for (int i = 1; i < n; i++) {
    dist.update(1, 1, n, l[e[i].v], r[e[i].v], e[i].c);
    toroot.update(1, 1, n, l[e[i].v], r[e[i].v], e[i].c);
  }
  for (int i = n; i <= m; i++)
    toroot.update(1, 1, n, l[e[i].u], l[e[i].u], e[i].c);
  int o, u, v;
  long long c;
  for (int i = 1; i <= q; i++) {
    read(o);
    read(u);
    if (o == 1) {
      read(c);
      if (u < n) {
        dist.update(1, 1, n, l[e[u].v], r[e[u].v], c - e[u].c);
        toroot.update(1, 1, n, l[e[u].v], r[e[u].v], c - e[u].c);
      } else
        toroot.update(1, 1, n, l[e[u].u], l[e[u].u], c - e[u].c);
      e[u].c = c;
    } else {
      read(v);
      if (l[u] <= l[v] && r[u] >= l[v])
        writeln(dist.getelement(1, 1, n, l[v]) -
                dist.getelement(1, 1, n, l[u]));
      else
        writeln(toroot.get(1, 1, n, l[u], r[u]) -
                dist.getelement(1, 1, n, l[u]) +
                dist.getelement(1, 1, n, l[v]));
    }
  }
}