There are N cities in Eddy's neverland. There are some flights to connect some pair of cities. Except flight, there's no any other way to shuttle between cities.

However, in some cases, flight attendants may go on strike to fight for their rights. Therefore, some flight may be shut down for a period of time. On the other hand, some flight may come out to compete the market.

In Eddy's neverland, each flight must propose its expected cost to be granted the license to fly. Then, Eddy will choose some flights and grant them the licenses. In order to keep the neverland great, Eddy will choose a minimum total cost flights to grant the license such that each city is possible to connect to each other city by the granted flights.

The first line of input contains two space-separated integers N and Q, where N is the number of cities and Q is the number of events.

Following Q lines each contains four space-separated integers . If , there is a new flight coming out between city  and city  with cost . If , the flight attendants of the flight connecting city  and  with cost  has gone on strike and the flight is shut down.






It's guaranteed that if , the required flight exists.

Output Q lines each contains an integer representing the most flights needed to connect two cities in the chosen combination. If there exists two cities which can not be connected through the current flights, output .

It's guaranteed that the chosen combination will be unique.

3 6
1 1 2 1
1 1 3 2
1 2 3 4
1 1 2 8
0 1 2 1
0 2 3 4

-1
2
2
2
2
2

4 4
1 1 2 1
1 1 3 2
1 1 4 8
1 2 3 4

-1
-1
2
2

First two flights are not enough to make each pair of cities connected.

First three flights are enough to make each pair of cities connected. The most flights needed to connect some pair of cities results from connecting city 2 and city 3 which needs two flights to connect(so as city 2 and city 4, city 3 and city 4).
The forth flights won't be included in the chosen combination. The scenario remains the same.