401435: GYM100451 D Olympic Games in Berland

The International Olympic Committee has finally officially stated that the following Olympic Games will be held in one of the cities of Berland!

Naturally, the country isn't prepared for the Olympics, but there is plenty of time. For example, all roads in Berland are unpaved, but according to the IOC rules, the country of the Olympics must have all cities connected by high speed modern highways.

Berland has n cities, some pairs of the cities are connected by two-way unpaved roads. For each road, we know the time t_j we need to turn it into a high speed modern highway. All possible expences have been accounted for, so the top priority is to prepare the country for the Olympics as quickly as possible. The only possible way to build a highway is to upgrage an unpaved road.

The Olympic Committee of Berland decided to connect some cities by highways so that it was possible to get from each city to any other one using only highways. Note that you need to make the minimum possible number of highways. There are a lot of groups of workers involved, so the road works are conducted simultaneously. Thus, the road works will end in time equal to the maximum t_j among all roads with construction works.

The City of the Olympics hasn't been yet defined. However, the Olympic Committe of Berland has already decided that to minimize extra traffic, there should be exactly one highway attached to this city.

The analytical department is facing the complex task of planning the works. For each city i find the minimum time for road works considering that city i is the City of the Olympics.

The input contains one or multiple sets of test data separated by single line breaks.

Each set starts with a line that contains two integers n and m (2 ≤ n ≤ 4·10⁵, 0 ≤ m ≤ 4·10⁵), where n is the number of cities in Berland and m is the number of unpaved roads. All roads are bidirectional, each pair of cities has at most one road between them. Then follow m lines that describe the roads. Line j contains three integers x_j, y_j and t_j (1 ≤ x_j, y_j ≤ n) and shows that the j-th road connects cities x_j and y_j (x_j ≠ y_j), and it takes t_j (1 ≤ t_j ≤ 10⁹) time units to make a highway instead of this road.

It is guaranteed that the total number of roads for all test data doesn't exceed 4·10⁵, and the number of roads also doesn't exceed 4·10⁵.

For each set of test data print sequence T₁, T₂, ..., T_n, where T_i is the minimum possible time of ending the road works provided that the Olympiad will be held in city i. Print T_i =  - 1 if it is impossible to meet the requirements while conducting the Olympiad in city i.

Follow the format of the sample from the input.

4 6
1 2 2
2 3 3
3 1 1
3 4 1
4 1 2
4 2 10

3 3
1 2 1
2 3 1
3 1 2

3 2
1 2 2
2 3 4

Case 1: 3 2 2 2
Case 2: 1 2 1
Case 3: 4 -1 4