Crowd Control

A programming contest brings a large number of visitors to Amsterdam. Most of them arrive at the train station and then walk to the contest venue in one big parade, moving from intersection to intersection along the streets.

Each street allows only a certain number of people per hour to pass through. That number is the capacity of the street. The number of people going through a street must never exceed its capacity, because otherwise accidents happen. People may walk through a street in either direction.

The organizers prepare a single path from the train station to the venue. The capacity of a path is the minimum capacity of any street on the path, and the organizers choose the path with maximum capacity. So that nobody walks the wrong way, they close down every street that has one of its endpoints at an intersection on the path but is not itself part of the path.

You are given the graph of the streets and intersections of Amsterdam. Write a program that prints which streets must be closed down in order to create a single maximum-capacity path from the train station to the venue. The path must be simple, so it may not visit any intersection more than once.

The first line contains two integers $n$, the number of intersections in the city, and $m$, the number of streets ($1 \le n, m \le 1000$).

Each of the following $m$ lines describes one street with three integers $a_i$, $b_i$ and $c_i$, where $a_i$ and $b_i$ are the ids of the two intersections connected by this street ($0 \le a_i, b_i < n$) and $c_i$ is the capacity of this street ($1 \le c_i \le 500000$). Streets are numbered from $0$ to $m - 1$ in the given order.

The input always satisfies the following:

• All visitors start at the train station, which is the intersection with id $0$, and the venue is at the intersection with id $n - 1$.
• The intersections and streets form a connected graph.
• No two streets connect the same pair of intersections.
• No street has the same intersection at both ends.
• The simple path of maximum capacity is unique.

Print one line with the numbers of the streets that must be blocked in order to create a single maximum-capacity path from the train station to the venue, separated by single spaces. Sort the numbers in increasing order.

If no street must be blocked, print none instead.

The figure illustrates the first example input.