G. Sabotage
|
Zombies have a special point-to-point inter-zombie communication facility
with multiple channels per zombie, with limited range (using smelly pheromones).
When zombies are deployed in bigger quantity in large cities, they need
to build a network and relay messages so that any zombie can send
messages to any other zombie.
Instead of redundancy, they go for low latency so from a possible set of connections between zombie pairs they select some so that the sum of the latency of the selected ones is minimal and all zombies can communicate in the network by routing messages along the selected connections. |
http://upload.wikimedia.org/wikipedia/commons/2/24/Network_Tree_diagram.png |
Your task is to ruin the zombie network by blocking a few point-to-point connections in a way that the resulting zombie network will have worse latency than the original one. Zombies reconfigure their network as soon as some of their selected connections are blocked and they keep the sum of the latencies to a minimum at all times.
Blocking a connection is expensive, you need to minimize the total cost of your blocking operation.
Input
First line contains N and M the number of zombies and the number of possible network connections, the following M lines each describe a connection with four integers: A, B, L, C, that is a connection between the A,B zombies with latency L and blocking cost C. (Zombies are indexed from 0, the latency of a connection is a fixed value, the same pair of zombies may have several different potential connections between them with different parameters.)
Output
The first line is the minimum cost of the blocking operation.
The next line should contain a list of edge indices, the connections which should be blocked. (After the listed connections are blocked the minimum sum latency achievable in the remaning network should be greater than originally. Edges are indexed from 0 in the order they appear in the input.)
Example input4 7 0 1 1 3 0 2 1 9 0 3 2 1 1 2 2 2 1 3 2 1 2 3 2 2 2 3 3 3 | Example output3 0 |