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 areas connected by roads such that it is possible to travel from any area to any other using these roads. The -th road connects areas and , and it takes seconds to travel it in either direction. The target attraction of your trip is the maid café located in area .
In order to properly plan out your trip, you need to estimate how long it would take to go from certain areas to area . 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 of the following events:
1 u: A previously uncrowded area becomes crowded.
2 u: You need to determine the minimum possible expected travel time from area to area in the current state of all the areas.
For all events, .
Subtask 1 [30%]
1 events occur before all type
Subtask 2 [70%]
No additional constraints.
The first line contains integers and .
The next lines each contain integers , , and .
The next 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