ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Urban Geography

Time limit: 1.5 second
Memory limit: 128 MB
Android Vasya prepares a project in Urban geography. The aim of the project is to improve the infrasructure of the city he lives in.
Now the city consists of n districts, some of which are connected by roads. Using these roads one can get from any district to any other district of the city by car. Vasya thinks that such big amount of roads makes citizens use their own cars instead of walking or cycling. He wants to close as many roads for cars as possible and turn them into boulevards. Of course, Vasya wants to keep the possibility to get from any district to any other district of the city by car using roads.
Now citizens pay for using roads, and prices for different roads may vary very much. Vasya thinks that leaving open some expensive and some cheap roads at the same time is not a good idea beacuse it can increase social tension in the city. That’s why he wants to minimize the price spread between the most expensive and the cheapest roads. Help Vasya choose the roads to keep open.


The first line contains integers n и m that are the number of city districts and roads correspondingly (2 ≤ n ≤ 50 000; n − 1 ≤ m ≤ 50 000). The next m lines contain triples of integers ai, bi and ci, meaning that between the city districts ai and bi there is a road with the price ci (1 ≤ ai, bin; aibi; 1 ≤ ci ≤ 109). There can be several roads between two districts.


In the only line output the sequence of integers — numbers of the roads which should be kept open in the city. The roads are numbered as they appear in the input data. If there are several solutions, output any of them.


3 3
1 2 1
2 3 3
3 1 4
2 3
4 5
1 2 1
2 3 1
1 3 2
1 4 2
2 4 1
1 2 5
Problem Author: Nikita Burlakov
Problem Source: Ural Sport Programming Championship 2015
To submit the solution for this problem go to the Problem set: 2055. Urban Geography