Network Wars
The computer network in Byteland consists of n computers linked by m fiber optic cables. Each cable connects two computers and allows data to flow in both directions. Among these computers, two are particularly significant: one has internet access, and the other is linked to the presidential residence.
The computer connected to the presidential residence is labeled as 1, while the one with internet access is labeled as n.
Recently, the company Max Traffic has decided to take control of certain connections to monitor data transmitted from the presidential residence. Naturally, Max Traffic aims to control a set of connections such that all data sent from the internet to the presidential residence passes through at least one of these controlled connections.
To execute their plan, the company needs to purchase these connections from their current owners. Each connection has a specific cost. Since the company primarily focuses on providing internet services rather than espionage, the management wants to minimize the average purchase price. If the company buys k connections with a total cost of c, they need to minimize the value of c=k.
Input
The first line of the input file contains the integers n (2 ≤ n ≤ 100) and m (1 ≤ m ≤ 400). The following m lines describe the connections, with each cable specified by three integers: the numbers of the computers it connects and the purchase cost. The cost of each connection is positive and does not exceed 10^7.
There is at most one cable connecting any two computers, and no computer is connected to itself. It is guaranteed that the network is connected, meaning data can be transmitted between any two computers through the network.
Output
On the first line, output the number of connections that need to be purchased. On the second line, output the indices of these connections. Connections are numbered starting from 1 in the order they are provided in the input file.