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