The Flyover Construction |

The newly elected Mayor of Dhaka is taking a new project to reduce the trafffic jam of the megacity. In a meeting the engineers have decided to construct the first Flyover in Dhaka. As the budget is limited only one flyover can be constructed. Now the problem faced by them is which road will be selected. As there are so many important roads in Dhaka, it is not so easy job to find the optimal one. Moreover they have to also consider about the future. Finally they have got a new scheme considering the following assumptions.

- Dhaka can be considered as an undirected graph. Several places like Agargaon, Farmget, Motijheel etc are the nodes of this graph and roads are the edges. Each road is associated with some cost.
- A route in Dhaka is a path from one place to another place. Such as Agargaon to Motijheel or Motijheel to Agargaon.
- People of Dhaka always use the minimum cost Path.
- If there are several minimum paths available for a route then they use each one.

Using the above technique it is possible to find out a road which is used for maximum number of routes. If several roads satisfy this criteria the Mayor will choose the final one.

In the above graph road AC is used for route AC,AD,AB. Road AB is used for AB route only. Road BD is used for route BD,BC,BA. Road CD is used for route AD,AB,BC,CD. Thus road CD is maximum used.

The input will start with two postive integer V,E ( 1<=V<=100) indicates the number of places in Dhaka and number of roads available. Each place is recognized by a unique integer from 1 to N. The next M lines contain 3 integers s,t,C (s!=t) each. It means there is a road between s and t associated with cost C.

Input is terminated by EOF.

For each data set print the road index which is maximum used. If several roads satisfy the condition show all using sorted order of index. One line is used for each case.

4 4 1 2 20 1 4 1 2 3 3 3 4 4 4 4 1 2 1 1 4 1 2 3 1 3 4 1

4 1 2 3 4

## Md. Kamruzzaman