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, bi ≤ n; ai ≠ bi; 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.
1 2 1
2 3 3
3 1 4
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