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 MAX = 1 << 19, TOUR = 1 << 19;
const long long INF = 1e18;
int n, q;
pair<int, int> e[MAX];
int w[MAX];
int disc[MAX], fin[MAX], vr = 0;
long long odroota[MAX];
int tko[MAX];
vector<pair<int, int> > V[MAX];
int moj_ind[MAX];
struct node {
  long long mn, prop;
} t[2 * TOUR];
void propagiraj(int pos) {
  long long pr = t[pos].prop;
  if (!pr) return;
  for (int i = (2 * pos); i < (2 * pos + 2); i++) {
    t[i].mn += pr;
    t[i].prop += pr;
  }
  t[pos].prop = 0;
}
void stavi(int pos, int lo, int hi, int begin, int end, long long val) {
  if (lo >= end || hi <= begin) return;
  if (lo >= begin && hi <= end) {
    t[pos].prop += val;
    t[pos].mn += val;
    return;
  }
  propagiraj(pos);
  stavi(2 * pos + 0, lo, (lo + hi) / 2, begin, end, val);
  stavi(2 * pos + 1, (lo + hi) / 2, hi, begin, end, val);
  t[pos].mn = min(t[2 * pos].mn, t[2 * pos + 1].mn);
}
long long vrati(int pos, int lo, int hi, int begin, int end) {
  if (lo >= end || hi <= begin) return INF;
  if (lo >= begin && hi <= end) return t[pos].mn;
  propagiraj(pos);
  return min(vrati(2 * pos + 0, lo, (lo + hi) / 2, begin, end),
             vrati(2 * pos + 1, (lo + hi) / 2, hi, begin, end));
}
void dfs(int node, int pros, long long dosad) {
  tko[vr] = node;
  disc[node] = vr++;
  odroota[node] = dosad;
  for (auto it : V[node])
    if (it.first != pros) dfs(it.first, node, dosad + it.second);
  fin[node] = vr;
}
void init() {
  for (int i = 0; i < TOUR; i++) {
    long long val = INF;
    if (i < n) val = odroota[tko[i]] + w[moj_ind[tko[i]]];
    t[i + TOUR].mn = val;
  }
  for (int i = TOUR - 1; i; i--) t[i].mn = min(t[2 * i].mn, t[2 * i + 1].mn);
}
long long do_mene(int x) {
  if (!x) return 0;
  return vrati(1, 0, TOUR, disc[x], disc[x] + 1) - w[moj_ind[x]];
}
int main() {
  scanf("%d%d", &n, &q);
  moj_ind[0] = MAX - 1;
  for (int i = 0; i < 2 * n - 2; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    e[i] = pair<int, int>(a, b);
    w[i] = c;
    if (i < n - 1) {
      V[a].push_back({b, c});
      V[b].push_back({a, c});
    } else
      moj_ind[a] = i;
  }
  dfs(0, -1, 0);
  init();
  for (; q--;) {
    int st;
    scanf("%d", &st);
    if (st == 1) {
      int ind, novw;
      scanf("%d%d", &ind, &novw);
      ind--;
      int prom = novw - w[ind];
      w[ind] = novw;
      if (ind < n - 1) {
        int donji = e[ind].second;
        stavi(1, 0, TOUR, disc[donji], fin[donji], (long long)prom);
      } else {
        int ja = e[ind].first;
        assert(moj_ind[ja] == ind);
        stavi(1, 0, TOUR, disc[ja], disc[ja] + 1, (long long)prom);
      }
    } else {
      int a, b;
      scanf("%d%d", &a, &b);
      a--;
      b--;
      long long rje = INF;
      if (disc[b] >= disc[a] && disc[b] < fin[a]) {
        long long doa = do_mene(a), dob = do_mene(b);
        rje = dob - doa;
      } else {
        long long moj_put = vrati(1, 0, TOUR, disc[a], fin[a]) - do_mene(a);
        long long dob = do_mene(b);
        rje = moj_put + dob;
      }
      printf("%lld\n", rje);
    }
  }
  return 0;
}