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.
~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%]
1 events occur before all type
Subtask 2 [70%]
No additional constraints.
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.
For each type
2 event, output the answer (in seconds) on a new line.
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
6 24 0