DMOPC '21 Contest 3 P5 - Crowded Travels

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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.

Constraints

For all events, .

All type 1 events occur before all type 2 events.

Input Specification

The first line contains integers and .

The next lines each contain integers , , and .

The next 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