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 = 2e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
vector<pair<int, int> > v[maxn];
pair<int, int> seg[maxn];
long long sm[maxn], up[maxn];
int C = 1, n, a[2 * maxn], b[2 * maxn], c[2 * maxn];
struct Segment {
  long long val[4 * maxn], lazy[4 * maxn];
  Segment() {
    memset(val, 0, sizeof val);
    memset(lazy, 0, sizeof lazy);
  }
  void get(int l, int r, int ind) {
    val[ind] += lazy[ind];
    if (l != r) {
      lazy[2 * ind] += lazy[ind];
      lazy[2 * ind + 1] += lazy[ind];
    }
    lazy[ind] = 0;
  }
  void add(int f, int s, int x, int l = 1, int r = n, int ind = 1) {
    if (f > s || l > r) return;
    get(l, r, ind);
    if (s < l || r < f) return;
    if (f <= l && r <= s) {
      lazy[ind] += x;
      get(l, r, ind);
      return;
    }
    int mid = (l + r) >> 1;
    add(f, s, x, l, mid, 2 * ind);
    add(f, s, x, mid + 1, r, 2 * ind + 1);
    val[ind] = min(val[2 * ind], val[2 * ind + 1]);
  }
  long long ask(int f, int s, int l = 1, int r = n, int ind = 1) {
    if (f > s || l > r) return inf;
    get(l, r, ind);
    if (s < l || r < f) return inf;
    if (f <= l && r <= s) return val[ind];
    int mid = (l + r) >> 1;
    return min(ask(f, s, l, mid, 2 * ind), ask(f, s, mid + 1, r, 2 * ind + 1));
  }
};
Segment segm1, segm2;
void dfs(int u, int par = -1) {
  seg[u].first = C++;
  for (pair<int, int> p : v[u]) {
    if (p.first != par) {
      sm[p.first] = sm[u] + p.second;
      dfs(p.first, u);
      sm[p.first] = p.second;
    }
  }
  seg[u].second = C - 1;
  segm1.add(seg[u].first, seg[u].first, sm[u]);
  segm2.add(seg[u].first, seg[u].first, sm[u]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) {
    cin >> a[i] >> b[i] >> c[i];
    v[a[i]].push_back({b[i], c[i]});
    v[b[i]].push_back({a[i], c[i]});
  }
  dfs(1);
  for (int i = n; i <= 2 * n - 2; i++) {
    cin >> a[i] >> b[i] >> c[i];
    up[a[i]] = c[i];
    segm1.add(seg[a[i]].first, seg[a[i]].first, up[a[i]]);
  }
  while (q--) {
    int task, A, B;
    cin >> task >> A >> B;
    if (task == 1) {
      if (b[A] == 1) {
        segm1.add(seg[a[A]].first, seg[a[A]].first, B - up[a[A]]);
        up[a[A]] = B;
      } else {
        segm1.add(seg[b[A]].first, seg[b[A]].second, B - sm[b[A]]);
        segm2.add(seg[b[A]].first, seg[b[A]].second, B - sm[b[A]]);
        sm[b[A]] = B;
      }
    } else {
      long long Ans1 = inf, Ans2 = inf;
      if (seg[A].first <= seg[B].first && seg[B].second <= seg[A].second)
        Ans1 = segm2.ask(seg[B].first, seg[B].first) -
               segm2.ask(seg[A].first, seg[A].first);
      Ans2 = segm1.ask(seg[A].first, seg[A].second) -
             segm2.ask(seg[A].first, seg[A].first) +
             segm2.ask(seg[B].first, seg[B].first);
      cout << min(Ans1, Ans2) << "\n";
    }
  }
  return 0;
}