Network Wars#4591
The computer network of Byteland consists of computers connected by fiber optic cables. Each cable connects exactly two computers and can transmit data in both directions. There are two especially important computers in the network: one provides access to the internet, and the other is connected to the presidential residence.
The computer connected to the presidential residence is assigned number , and the internet-connected computer has number .
Recently, the company Max Traffic decided to take control of some connections in order to monitor all data transmissions from the internet to users in the presidential residence. Of course, Max Traffic wants to control a set of connections such that all data traveling from the internet to the presidential residence must pass through at least one of these controlled connections.
To execute this plan, the company must buy the selected connections from their current owners. Each connection has a specific purchase cost. Since the company's main business is not espionage, but providing internet services, they wish to minimize the total purchase cost. If the company buys connections at a total cost , they must minimize the value of .
The first line contains two integers: - (2 \leq n \leq 100): the number of computers - (1 \leq m \leq 400): the number of fiber optic cables
The following lines each describe a cable with three integers: the numbers of the two computers it connects and its purchase cost. Each cost is positive and does not exceed 10^7.
No two computers are connected by more than one cable, and no cable connects a computer to itself. It is guaranteed that the network is connected: data can be transmitted between any two computers through the cables.
Output the number of connections to be purchased on the first line. On the second line, output the indices of these connections. Connections are numbered from in the order given in the input file.
Example 1