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;
int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
template <class T>
inline T biton(T n, T pos) {
  return n | ((T)1 << pos);
}
template <class T>
inline T bitoff(T n, T pos) {
  return n & ~((T)1 << pos);
}
template <class T>
inline T ison(T n, T pos) {
  return (bool)(n & ((T)1 << pos));
}
template <class T>
inline T gcd(T a, T b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
template <typename T>
string NumberToString(T Number) {
  ostringstream second;
  second << Number;
  return second.str();
}
inline int nxt() {
  int aaa;
  scanf("%d", &aaa);
  return aaa;
}
inline long long int lxt() {
  long long int aaa;
  scanf("%lld", &aaa);
  return aaa;
}
inline double dxt() {
  double aaa;
  scanf("%lf", &aaa);
  return aaa;
}
template <class T>
inline T bigmod(T p, T e, T m) {
  T ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % m;
    p = (p * p) % m;
  }
  return (T)ret;
}
vector<pair<long long int, long long int> > adj[1000010];
tuple<int, int, long long int> ar[1000010];
long long int reverse_cost[1000010];
vector<long long int> Sum;
int st[1000010], ed[1000010];
int Time = 1;
void dfs(int u, long long int d) {
  Sum.push_back(d + reverse_cost[u]);
  st[u] = Time++;
  for (auto it : adj[u]) {
    dfs(it.first, d + it.second);
  }
  ed[u] = Time - 1;
}
struct info {
  long long int sum;
  long long int lazy;
  long long int mn;
} tree[1000010 * 4];
void segment_tree(int node, int low, int high) {
  if (low == high) {
    tree[node].sum = Sum[low];
    tree[node].mn = Sum[low];
    return;
  }
  int left = 2 * node;
  int right = 2 * node + 1;
  int mid = (low + high) / 2;
  segment_tree(left, low, mid);
  segment_tree(right, mid + 1, high);
  tree[node].sum = tree[left].sum + tree[right].sum;
  tree[node].mn = min(tree[left].mn, tree[right].mn);
}
void propagate(int node, int low, int hi) {
  int left = 2 * node;
  int right = left + 1;
  int mid = (low + hi) / 2;
  tree[node].sum += (hi - low + 1) * tree[node].lazy;
  tree[node].mn += tree[node].lazy;
  if (hi != low) {
    tree[left].lazy += tree[node].lazy;
    tree[right].lazy += tree[node].lazy;
  }
  tree[node].lazy = 0;
  tree[node].lazy = 0;
}
void update(int node, int low, int hi, int i, int j, int value) {
  int left = 2 * node;
  int right = left + 1;
  if (tree[node].lazy) propagate(node, low, hi);
  if (hi < i || j < low) return;
  if (low >= i && hi <= j) {
    tree[node].sum += (hi - low + 1) * value;
    tree[node].mn += value;
    if (hi != low) {
      tree[left].lazy += value;
      tree[right].lazy += value;
    }
    tree[node].lazy = 0;
    return;
  }
  int mid = (low + hi) / 2;
  update(left, low, mid, i, j, value);
  update(right, mid + 1, hi, i, j, value);
  tree[node].sum = tree[left].sum + tree[right].sum;
  tree[node].mn = min(tree[left].mn, tree[right].mn);
}
long long int query(int node, int low, int hi, int i) {
  int left = 2 * node;
  int right = left + 1;
  if (tree[node].lazy) propagate(node, low, hi);
  if (low == hi) return tree[node].sum;
  int mid = (low + hi) / 2;
  if (i <= mid)
    return query(left, low, mid, i);
  else
    return query(right, mid + 1, hi, i);
}
long long int GetMin(int node, int low, int hi, int i, int j) {
  int left = 2 * node;
  int right = left + 1;
  if (tree[node].lazy) propagate(node, low, hi);
  if (hi < i || j < low) return LLONG_MAX;
  if (low >= i && hi <= j) return tree[node].mn;
  int mid = (low + hi) / 2;
  long long int x = GetMin(left, low, mid, i, j);
  long long int y = GetMin(right, mid + 1, hi, i, j);
  return min(x, y);
}
int main() {
  Sum.push_back(0);
  int n = nxt();
  int q = nxt();
  int x = 1;
  for (int i = 0; i < n - 1; i++) {
    int a = nxt();
    int b = nxt();
    long long int cost = lxt();
    adj[a].push_back(make_pair(b, cost));
    ar[x++] = make_tuple(a, b, cost);
  }
  for (int i = 0; i < n - 1; i++) {
    int a = nxt();
    int b = nxt();
    long long int cost = lxt();
    ar[x++] = make_tuple(a, b, cost);
    reverse_cost[a] = cost;
  }
  dfs(1, 0);
  segment_tree(1, 1, n);
  while (q--) {
    int t = nxt();
    if (t == 1) {
      int ind = nxt();
      long long int cost = lxt();
      int u = get<0>(ar[ind]);
      int v = get<1>(ar[ind]);
      if (ind > n - 1) {
        update(1, 1, n, st[u], st[u], -reverse_cost[u]);
        reverse_cost[u] = cost;
        update(1, 1, n, st[u], st[u], reverse_cost[u]);
        get<2>(ar[ind]) = cost;
      } else {
        update(1, 1, n, st[v], ed[v], -get<2>(ar[ind]));
        get<2>(ar[ind]) = cost;
        update(1, 1, n, st[v], ed[v], +get<2>(ar[ind]));
      }
    } else {
      int u = nxt();
      int v = nxt();
      long long int mn = LLONG_MAX;
      if (st[v] >= st[u] && st[v] <= ed[u]) {
        mn = (query(1, 1, n, st[v]) - reverse_cost[v]) -
             (query(1, 1, n, st[u]) - reverse_cost[u]);
      } else {
        mn = GetMin(1, 1, n, st[u], ed[u]) -
             (query(1, 1, n, st[u]) - reverse_cost[u]);
        mn += (query(1, 1, n, st[v]) - reverse_cost[v]);
      }
      printf("%lld\n", mn);
    }
  }
  return 0;
}