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 ≤ 105, 1 ≤ q ≤ 105).
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 ≤ 109).
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 ≤ 109).
Output
Print the answer to each query of second type in one line.