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 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 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 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 i-th cable by the new one. Of course, after replacing the i-th 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.

The first line contains a single integer n (2 ≤ n ≤ 10⁵), n is the number of computers in the network. Then n-1 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⁴), where a_i,b_i are numbers of computers connected by the i-th cable, t_i is the average transmission time of a packet through the cable and p_i 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.

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