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, .

##### 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 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
```

## Comments