rasta-in-tavaspolis

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^5, 1 ≤ q ≤ 10^5).

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^9).

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^9).

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

SAMPLE INPUT
5 6
1 2 8
2 3 1
2 4 3
3 5 2
2 4
2 3
1 1 2 2
2 4
2 3
2 1

SAMPLE OUTPUT
11
11
6
6
5

Source: hackerearth | Difficulty: HARD
Tags: Graph algorithms

Data structures

Divide and conquer


Solutions: