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>
namespace Main {
namespace Source {
template <typename T>
inline const void swap(T& a, T& b) {
  const T c(a);
  a = b, b = c;
}
template <typename T>
inline const T min(const T& a, const T& b) {
  return b < a ? b : a;
}
template <typename T>
inline const void amin(T& a, const T& b) {
  a = min(a, b);
}
class segment_tree {
  struct node {
    long long signed int value, lazy;
    node() : value(), lazy() {}
    node(const long long signed int value) : value(value), lazy(0) {}
  } * o;
  unsigned int n;
  static inline const unsigned int middle(const unsigned int l,
                                          const unsigned int r) {
    return (l + r) / 2;
  }
  static inline const unsigned int ld(const unsigned int x) { return x << 1; }
  static inline const unsigned int rd(const unsigned int x) {
    return x << 1 bitor 1;
  }
  inline const void upto(const unsigned int x) {
    o[x].value = min(o[ld(x)].value, o[rd(x)].value) + o[x].lazy;
  }
  inline const void build(
      const unsigned int x, const unsigned int l, const unsigned int r,
      const long long unsigned int (*f)(const unsigned int)) {
    if (r - l == 1) return (const void)(o[x] = node(f(l)));
    const unsigned int m(middle(l, r));
    build(ld(x), l, m, f), build(rd(x), m, r, f), upto(x);
  }
  inline const void modify(const unsigned int x, const unsigned int l,
                           const unsigned int r, const unsigned int tl,
                           const unsigned int tr,
                           const long long signed int t) {
    if (tl <= l and r <= tr)
      return (const void)(o[x].lazy += t, o[x].value += t);
    const unsigned int m(middle(l, r));
    if (tl < m) modify(ld(x), l, m, tl, tr, t);
    if (tr > m) modify(rd(x), m, r, tl, tr, t);
    upto(x);
  }
  inline const long long signed int query(const unsigned int x,
                                          const unsigned int l,
                                          const unsigned int r,
                                          const unsigned int tl,
                                          const unsigned int tr) {
    if (tl <= l and r <= tr) return o[x].value;
    const unsigned int m(middle(l, r));
    long long signed int re(0x7fffFFFFffffFFFFll);
    if (tl < m) amin(re, query(ld(x), l, m, tl, tr));
    if (tr > m) amin(re, query(rd(x), m, r, tl, tr));
    return re + o[x].lazy;
  }

 public:
  segment_tree() : o(NULL), n(0) {}
  compl segment_tree() {
    if (o) delete[] o;
  }
  inline const void build(const unsigned int n, const long long unsigned int (
                                                    *f)(const unsigned int)) {
    if (o) delete[] o;
    o = new node[n * 4](), build(1, 0, this->n = n, f);
  }
  inline const void modify(const unsigned int x, const signed int t) {
    modify(1, 0, n, x, x + 1, t);
  }
  inline const void modify(const unsigned int l, const unsigned int r,
                           const signed int t) {
    modify(1, 0, n, l, r, t);
  }
  inline const long long unsigned int query(const unsigned int x) {
    return query(1, 0, n, x, x + 1);
  }
  inline const long long unsigned int query(const unsigned int l,
                                            const unsigned int r) {
    return query(1, 0, n, l, r);
  }
};
}  // namespace Source
using namespace Source;
enum { N = 200000, Log = 17 };
static unsigned int n, q;
namespace Tree {
struct edge;
struct node {
  long long unsigned int depth;
  unsigned int dfn, first, l, r;
  struct nedge {
    edge* e;
    nedge* next;
    nedge(edge* const e, nedge* const next = NULL) : e(e), next(next) {}
  } * head;
  inline const void add(edge* const e) { head = new nedge(e, head); }
} static o[N + 1];
struct edge {
  unsigned int s, t, w;
  edge() {}
  edge(const unsigned int s, const unsigned int t, const unsigned int w)
      : s(s), t(t), w(w) {}
  inline const void change_tree(const unsigned int);
  inline const void change_1(const unsigned int);
} static e[N * 2];
static unsigned int id[N];
static segment_tree tre, cyc;
static unsigned int st[Log + 2][N * 2];
static unsigned int el, sl;
inline const void edge::change_tree(const unsigned int tar) {
  tre.modify(o[t].l, o[t].r, (const signed int)tar - (const signed int)w),
      cyc.modify(o[t].l, o[t].r, (const signed int)tar - (const signed int)w),
      w = tar;
}
inline const void edge::change_1(const unsigned int tar) {
  cyc.modify(o[s].dfn, (const signed int)tar - (const signed int)w), w = tar;
}
static inline const long long unsigned int depth(const unsigned int x) {
  return o[id[x]].depth;
}
static inline const long long unsigned int cycle(const unsigned int x) {
  return id[x] == 1 ? 0 : o[id[x]].depth + o[id[x]].head->e->w;
}
static inline const unsigned int mindep(const unsigned int a,
                                        const unsigned int b) {
  return o[b].depth < o[a].depth ? b : a;
}
static const void search(const unsigned int x, const unsigned int m,
                         const long long unsigned int depth,
                         unsigned int& dfn) {
  o[x].depth = depth, id[o[x].l = o[x].dfn = dfn++] = x,
  st[0][o[x].first = sl++] = x;
  for (node::nedge* i(o[x].head); i; i = i->next)
    if (i->e->t != 1 and i->e->t != m)
      search(i->e->t, x, depth + i->e->w, dfn), st[0][sl++] = x;
  o[x].r = dfn;
}
static inline const void add(const unsigned int s, const unsigned int t,
                             const unsigned int w) {
  o[s].add(&(e[++el] = edge(s, t, w)));
}
static inline const void read() {
  for (register unsigned int i(0); i < 2 * n - 2; ++i) {
    static unsigned int a, b, c;
    scanf("%u%u%u", &a, &b, &c);
    add(a, b, c);
  }
}
static inline const void search() {
  unsigned int t(0);
  search(1, 0, 0, t);
}
static inline const void init() {
  read(), search(), tre.build(n, depth), cyc.build(n, cycle);
  for (short unsigned int i(1); i <= Log + 1; ++i)
    for (register unsigned int j(0); j + (1 << i) - 1 < sl; ++j)
      st[i][j] = mindep(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
static inline const unsigned int lca(unsigned int x, unsigned int y) {
  x = o[x].first, y = o[y].first;
  if (y < x) swap(x, y);
  const short unsigned int t(log2(y - x + 1));
  return mindep(st[t][x], st[t][y - (1 << t) + 1]);
}
static inline const void change() {
  static unsigned int i, w;
  scanf("%u%u", &i, &w);
  if (i <= n - 1)
    e[i].change_tree(w);
  else
    e[i].change_1(w);
}
static inline const void print() {
  static unsigned int u, v;
  scanf("%u%u", &u, &v);
  long long unsigned int res(tre.query(o[v].dfn) - tre.query(o[u].dfn));
  if (lca(u, v) not_eq u) res += cyc.query(o[u].l, o[u].r);
  printf("%llu\n", res);
}
}  // namespace Tree
static inline const void main() {
  scanf("%u%u", &n, &q), Tree::init();
  for (register unsigned int i(0); i < q; ++i) {
    static short unsigned int t;
    scanf("%hu", &t);
    switch (t) {
      case 1:
        Tree::change();
        break;
      case 2:
        Tree::print();
        break;
    }
  }
}
}  // namespace Main
signed int main() {
  Main::main();
  return 0;
}