See Russian translation

Rasta lives in Tavaspolis. Tavasplois has n cities connected by n - 1 bidirectional roads. One can travel from any city to any other city using only these roads. Also, each road has a length.

You are given the information about this country. Also you are asked by Rasta to perform q queries. There are two types of queries:

1 v u w : Set the length of the road between cities v and u equal to w (v-u is a valid road).

2 v : Print the length of the longest simple path passing throght v (maybe v is one of its endpoints).

A simple path is a path that has no repeated vertex. Also, the length of a path is the sum of length of its roads.

Input format

The first line of input contains two integers, n and q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵).

In the next n - 1 lines you are given the information of the roads. Each line has three integers: v, u, w, endpoints and weight of a road (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ w ≤ 10⁹).

In the next q lines you are given the queries, in format 1 v u w or 2 v (1 ≤ v, u ≤ n, 1 ≤ w ≤ 10⁹).

Output

Print the answer to each query of second type in one line.