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>
#pragma GCC optimize("O0")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("-ffloat-store")
using namespace std;
long long n, m, a, b, c, k, temp, x, y;
const int MAXN = 100000 + 11;
inline vector<long long> read(int n);
inline long long max(long long a, long long b);
inline long long min(long long a, long long b);
inline long long gcd(long long a, long long b);
vector<pair<long long, long long>> v[200001];
vector<vector<int>> adj;
struct LCA {
  vector<int> height, euler, first, segtree;
  vector<bool> visited;
  int n;
  LCA(vector<vector<int>> &adj, int root = 0) {
    n = adj.size();
    height.resize(n);
    first.resize(n);
    euler.reserve(n * 2);
    visited.assign(n, false);
    dfs(adj, root);
    int m = euler.size();
    segtree.resize(m * 4);
    build(1, 0, m - 1);
  }
  void dfs(vector<vector<int>> &adj, int node, int h = 0) {
    visited[node] = true;
    height[node] = h;
    first[node] = euler.size();
    euler.push_back(node);
    for (auto to : adj[node]) {
      if (!visited[to]) {
        dfs(adj, to, h + 1);
        euler.push_back(node);
      }
    }
  }
  void build(int node, int b, int e) {
    if (b == e) {
      segtree[node] = euler[b];
    } else {
      int mid = (b + e) / 2;
      build(node << 1, b, mid);
      build(node << 1 | 1, mid + 1, e);
      int l = segtree[node << 1], r = segtree[node << 1 | 1];
      segtree[node] = (height[l] < height[r]) ? l : r;
    }
  }
  int query(int node, int b, int e, int L, int R) {
    if (b > R || e < L) return -1;
    if (b >= L && e <= R) return segtree[node];
    int mid = (b + e) >> 1;
    int left = query(node << 1, b, mid, L, R);
    int right = query(node << 1 | 1, mid + 1, e, L, R);
    if (left == -1) return right;
    if (right == -1) return left;
    return height[left] < height[right] ? left : right;
  }
  int lca(int u, int v) {
    int left = first[u], right = first[v];
    if (left > right) swap(left, right);
    return query(1, 0, euler.size() - 1, left, right);
  }
};
vector<int> e;
int intime[200001], mx[200001], timer = 0, inv[200001];
long long depth[200001], one[200001];
vector<long long> arr1(200001), arr2(200001);
void dfs(int u, long long dis = 0, int p = 0) {
  intime[u] = timer, mx[u] = intime[u];
  inv[u] = timer++;
  e.push_back(u);
  depth[u] = depth[p] + dis;
  for (const auto &x : v[u])
    dfs(x.first, x.second, u), mx[u] = max(mx[u], mx[x.first]);
}
struct ed {
  long long u, v, w;
} arr[400000];
class Segtree {
  int n;
  long long int *lzy, *t;

 public:
  Segtree(int n, const vector<long long> &a) {
    lzy = new long long int[4 * n];
    t = new long long int[4 * n];
    this->n = n;
    maketree();
    build(a, 1, 0, n - 1);
  }
  void maketree() {
    for (int i = 0; i < 4 * n; i++) lzy[i] = t[i] = 0;
  }
  void build(const vector<long long> &a, int v, int tl, int tr) {
    if (tl == tr)
      t[v] = a[tl];
    else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
  }
  void updateRange(int node, int start, int end, int l, int r, long long val) {
    if (lzy[node] != 0) {
      t[node] += lzy[node];
      if (start != end) {
        lzy[node * 2] += lzy[node];
        lzy[node * 2 + 1] += lzy[node];
      }
      lzy[node] = 0;
    }
    if (start > end or start > r or end < l) return;
    if (start >= l and end <= r) {
      t[node] += val;
      if (start != end) {
        lzy[node * 2] += val;
        lzy[node * 2 + 1] += val;
      }
      return;
    }
    int mid = (start + end) / 2;
    updateRange(node * 2, start, mid, l, r, val);
    updateRange(node * 2 + 1, mid + 1, end, l, r, val);
    t[node] = min(t[node * 2], t[node * 2 + 1]);
  }
  long long queryRange(int node, int start, int end, int l, int r) {
    if (start > end or start > r or end < l) return 1000000000000000000;
    if (lzy[node] != 0) {
      t[node] += lzy[node];
      if (start != end) {
        lzy[node * 2] += lzy[node];
        lzy[node * 2 + 1] += lzy[node];
      }
      lzy[node] = 0;
    }
    if (start >= l and end <= r) return t[node];
    int mid = (start + end) / 2;
    long long p1 = queryRange(node * 2, start, mid, l, r);
    long long p2 = queryRange(node * 2 + 1, mid + 1, end, l, r);
    return min(p1, p2);
  }
};
void solveforthiscase(const int &test) {
  int q;
  cin >> n >> q;
  adj.resize(n + 1);
  for (int i = 0; i < 2 * n - 2; i++) {
    cin >> a >> b >> c, arr[i + 1] = {a, b, c};
    if (i < n - 1)
      v[a].emplace_back(b, c), adj[a].push_back(b);
    else
      one[a] = c;
  }
  dfs(1);
  struct LCA tree(adj, 1);
  for (int i = 0; i < n; i++)
    arr1[i] = one[e[i]] + depth[e[i]], arr2[i] = depth[e[i]];
  class Segtree t1(n, arr1), t2(n, arr2);
  while (q--) {
    int type;
    cin >> type >> a >> b;
    if (type == 1) {
      int initial = arr[a].w;
      arr[a].w = b;
      if (a <= n - 1) {
        t2.updateRange(1, 0, n - 1, intime[arr[a].v], mx[arr[a].v],
                       arr[a].w - initial);
        t1.updateRange(1, 0, n - 1, intime[arr[a].v], mx[arr[a].v],
                       arr[a].w - initial);
      } else
        t1.updateRange(1, 0, n - 1, intime[arr[a].u], intime[arr[a].u],
                       arr[a].w - initial);
    }
    if (type == 2) {
      if (a == tree.lca(a, b))
        cout << t2.queryRange(1, 0, n - 1, intime[b], intime[b]) -
                    t2.queryRange(1, 0, n - 1, intime[a], intime[a])
             << '\n';
      else
        cout << t2.queryRange(1, 0, n - 1, intime[b], intime[b]) +
                    t1.queryRange(1, 0, n - 1, intime[a], mx[a]) -
                    t2.queryRange(1, 0, n - 1, intime[a], intime[a])
             << '\n';
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  cin.tie(NULL);
  cout.tie(NULL);
  clock_t start, end;
  start = clock();
  int test = 1;
  for (int i = 1; i <= test; i++) {
    solveforthiscase(i);
  }
  end = clock();
  long double time_taken =
      (long double)(end - start) / (long double)(CLOCKS_PER_SEC);
  if (false)
    cerr << "Time taken by program is : " << (long double)time_taken * 1000
         << " milisec ";
}
inline long long max(long long a, long long b) { return ((a > b) ? a : b); }
inline long long min(long long a, long long b) { return ((a > b) ? b : a); }
inline long long gcd(long long a, long long b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
inline vector<long long> read(int n) {
  vector<long long> v(n);
  for (int i = 0; i < v.size(); i++) cin >> v[i];
  return v;
}