403740: GYM101252 C Electrician

An electrician Vasya has got an assignment to solder n wires. His boss specified the requirements precisely, so for each wire Vasya knows exactly where its endpoints should be soldered to. Two identifiers a_i, b_i are given for each wire, meaning that one endpoint of the wire should be soldered to the place a_i, and the other endpoint should be soldered to the place b_i. It doesn't matter which endpoint will be soldered to which place. Also each wire has two more characteristics r_i and p_i, where r_i is its reliability and p_i is its cost.

The only way for Vasya to express himself in such a rigorous constraints is to choose an order, and solder all wires in this order, one after another. As an experienced electrician Vasya knows what a short circuit is — it occurs when a scheme contains a cycle, in other words when there is more than one simple path over wires from one place to another. So, if a short circuit occurs after a wire is soldered, the least reliable wire in the cycle burns out (you may think that the least reliable wire disappears from the scheme). If there are several least reliable wires in the cycle, the one of them which was soldered earlier burns out. It is clear that after a wire burns out, the scheme doesn't have any cycles.

When Vasya is done with soldering, he ends up with a scheme of soldered wires. So, he wants to solder all wires in such an order, that the total cost of wires in a resulting scheme will be as maximal as possible.

The first line of input contains a single integer n (1 ≤ n ≤ 30000). Each of the following n lines contains four integer numbers a_i, b_i, r_i, p_i (1 ≤ a_i, b_i, r_i, p_i ≤ 10⁹;a_i ≠ b_i), where a_i and b_i are identifiers of the places for endpoints of i-th wire, r_i is the reliability of the wire, and p_i is the cost of the wire. There can be more than one wire between any pair of places.

Print the required maximal total cost to the first line of output. Print the order of wires for soldering to the second line, delimiting wire indices with a single space.

You may print any solution if there are many of them.

4
10 20 5 3
20 11 5 2
10 11 7 1
1 2 1 1

5
2 3 1 4 

In the sample test Vasya can choose any order with the only rule: the second wire should be soldered before the first one. If he violates the rule, the total cost will be 4 instead of 5.