534. Computer Network
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
n1 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
t_{i}, which represents the average time to transmit a packet from computer
a_{i} to computer
b_{i} (or vice versa), where
a_{i},
b_{i} are computers connected by the
ith cable.
For two computers
a and
b the average time to transmit a packet from one computer to another is the sum of all
t_{i}'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
p_{i} was determined — the cost of replacing the
ith cable by the new one. Of course, after replacing the
ith cable, the new one will still connect computers
a_{i} and
b_{i}.
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.
Input
The first line contains a single integer
n (2 ≤
n ≤ 10
^{5}),
n is the number of computers in the network. Then
n1 lines contain descriptions of all cables in the form of four integers
a_{i},
b_{i},
t_{i},
p_{i} (1 ≤
a_{i},
b_{i} ≤
n; 1 ≤
t_{i},
p_{i} ≤ 10
^{4}), where
a_{i},
b_{i} are numbers of computers connected by the
ith cable,
t_{i} is the average transmission time of a packet through the cable and
p_{i} is the cost of replacing the
ith cable with a new one.
Output
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.
Example(s)
sample input

sample output

4
1 2 3 3
1 3 8 33
1 4 3 7

10
2
1 3

sample input

sample output

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

2
1
2
