462. Electrician
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
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.
Input
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
^{9};
a_{i} ≠q
b_{i}), where
a_{i} and
b_{i} are identifiers of the places for endpoints of
ith 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.
Output
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.
Example(s)
sample input

sample output

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

5
2 3 1 4

Note
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.