Time limit per test: 1 second(s) Memory limit: 262144 kilobytes
input: standard output: standard
Computer network of Berland's best physical and mathematical school has a "tree" topology. That is, the network has no cycles; it connects n computers by n-1 cables. Each cable connects exactly two different computers.
The school has really old equipment and the network is slow. The network administrator defined for each cable a value ti, which represents the average time to transmit a packet from computer ai to computer bi (or vice versa), where ai, bi are computers connected by the i-th cable.
For two computers a and b the average time to transmit a packet from one computer to another is the sum of all ti's for the cables on the path from a to b. Of course, an important characteristic of the network is the maximum possible average time of transmitting a packet between two computers. This characteristic is called .
In light of national innovations and modernizations it was decided to improve the school computer network and reduce the value of .
It was decided to replace some cables with new ones. New cables have such a high speed of data transmission that any packet passes through the cable in negligibly little time. In practice, the time of a packet transmission for new cables equals 0. For each cable its price pi was determined — the cost of replacing the i-th cable by the new one. Of course, after replacing the i-th cable, the new one will still connect computers ai and bi.
Help the network administrator to find such set of cables, that after they are replaced, the value of becomes less and the total cost of replacing these cables is minimal. Note that in this problem you do not have to minimize , but you should make it less than its initial value.
The first line contains a single integer n (2 ≤ n ≤ 105), n is the number of computers in the network. Then n-1 lines contain descriptions of all cables in the form of four integers ai, bi, ti, pi (1 ≤ ai,bi ≤ n; 1 ≤ ti,pi ≤ 104), where ai,bi are numbers of computers connected by the i-th cable, ti is the average transmission time of a packet through the cable and pi is the cost of replacing the i-th cable with a new one.
In the first line print the required minimum possible cost of replacements. In the second line print the number of cables in the required set in arbitrary order. In the third line print the numbers of these cables. Consider the cables numbered from 1 in the order they appear in the input. If there are multiple solutions, print any of them.
1 2 3 3
1 3 8 33
1 4 3 7
1 2 3 5
2 3 5 2
3 4 5 4
Codeforces (c) Copyright 2010-2023 Mike Mirzayanov