You got the once-in-a-lifetime chance to go to Tokyo right now! As Tokyo is a large city, you've split it into ~N~ areas connected by ~N-1~ roads such that it is possible to travel from any area to any other using these roads. The ~i~-th road connects areas ~a_i~ and ~b_i~, and it takes ~c_i~ seconds to travel it in either direction. The target attraction of your trip is the maid café located in area ~1~.

In order to properly plan out your trip, you need to estimate how long it would take to go from certain areas to area ~1~. Initially, all of the areas are uncrowded, and you may choose any neighbouring area as your next destination in an uncrowded area. However, Tokyo is a very busy city, so some areas may become crowded as the day progresses! In any crowded area you have no control over where you are headed, and will pick a neighbouring area uniformly at random as your next destination if you choose to leave the current area.

To ensure the success of your trip, write a program that supports ~Q~ of the following events:

• 1 u: A previously uncrowded area ~u~ becomes crowded.
• 2 u: You need to determine the minimum possible expected travel time from area ~u~ to area ~1~ in the current state of all the areas.

Constraints

~1 \le N, Q \le 3 \times 10^5~

~1 \le a_i, b_i \le N~

~1 \le c_i \le 10^6~

For all events, ~1 \le u \le N~.

Subtask 1 [30%]

All type 1 events occur before all type 2 events.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains ~2~ integers ~N~ and ~Q~.

The next ~N-1~ lines each contain ~3~ integers ~a_i~, ~b_i~, and ~c_i~.

The next ~Q~ lines each describe an event.

Output Specification

For each type 2 event, output the answer (in seconds) on a new line.

Sample Input

7 7
1 2 4
1 3 3
2 4 2
3 5 1
3 6 3
6 7 2
2 4
1 3
1 6
1 4
2 7
1 1
2 1

Sample Output

6
24
0