Bridges of Damaging Boss

You are given an undirected weighted graph representing n islands and m bridges. Each bridge connects two islands (possibly the same island, i.e. self‐loop) and has a weight which represents the damage the player takes in order to cross it. The player can only cross a bridge after defeating the enemies on it, incurring the corresponding damage. Additionally, an evil Boss will guard exactly one bridge, rendering it impassable. Due to the Boss's presence, the player must choose an alternative route from island 1 to island n in order to reach the destination.

Let the function \(f(e)\) denote the minimum total damage incurred when travelling from island 1 to island n in the graph after bridge \(e\) is removed. (The player always chooses the path with the smallest total damage.) The Boss, being evil, will choose to guard a bridge that maximizes \(f(e)\); that is, among all bridges, he picks one with the greatest minimum damage cost. (If removal of a bridge disconnects island 1 and island n, consider \(f(e)=\infty\); such a bridge is an optimal candidate.)

Your task is to determine all bridges that the Boss may choose to guard. Output their 1-indexed indices in ascending order, separated by spaces.

Note: The graph may contain multiple edges (parallel edges) and self-loops.

Mathematical formulation:

For each bridge \(e_i\) (\(1 \le i \le m\)), let \[ f(e_i)= \min_{path \ in\ G \setminus \{e_i\}} \sum_{edge\ j \in path} w_j, \] where \(w_j\) is the weight (damage) of bridge \(j\). If there is no path from island 1 to island n in \(G\setminus \{e_i\}\), then \(f(e_i)=\infty\). Let \[ M = \max_{1 \le i \le m} f(e_i). \] Output all indices \(i\) for which \(f(e_i)= M\).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of islands and bridges, respectively). The next \(m\) lines each contain three integers \(u\), \(v\) and \(w\), representing a bridge connecting islands \(u\) and \(v\) with a damage cost of \(w\). The islands are numbered from 1 to \(n\). Note that there may be multiple bridges connecting the same pair of islands and bridges that are self-loops.

outputFormat

Output a single line containing the 1-indexed indices of all bridges that maximize the minimum damage required to go from island 1 to island n (i.e. bridge candidates that the Boss may choose). The indices should be in ascending order and separated by a single space.

sample

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

1 2