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 ai, bi are given for each wire, meaning that one endpoint of the wire should be soldered to the place ai, and the other endpoint should be soldered to the place bi. It doesn't matter which endpoint will be soldered to which place. Also each wire has two more characteristics ri and pi, where ri is its reliability and pi 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 ai, bi, ri, pi (1 ≤ ai, bi, ri, pi ≤ 109;ai ≠ bi), where ai and bi are identifiers of the places for endpoints of i-th wire, ri is the reliability of the wire, and pi 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.
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.
## Input
The first line of input contains a single integer n (1 ≤ n ≤ 30000). Each of the following n lines contains four integer numbers ai, bi, ri, pi (1 ≤ ai, bi, ri, pi ≤ 109;ai ≠ bi), where ai and bi are identifiers of the places for endpoints of i-th wire, ri is the reliability of the wire, and pi 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.
[samples]
## 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.
**Definitions**
Let $ R, C \in \mathbb{Z} $ denote the number of rows and columns of the grid, with $ 1 \leq R, C \leq 100 $.
Let $ G = (g_{i,j})_{1 \leq i \leq R, 1 \leq j \leq C} $ be the grid, where each $ g_{i,j} \in \{>, -, |\} $.
The player starts at $ (1,1) $ and may only move right or down, ending at any cell $ (i,j) $ with $ i \leq R $, $ j \leq C $.
The player collects the symbol in each visited cell.
The player has an infinite supply of symbols $ \{x, o\} $.
A Hackatari logo is a multiset of five symbols: $ \{x, o, >, -, |\} $.
**Constraints**
1. The player’s path is a monotonic path from $ (1,1) $ to some $ (i,j) $, moving only right or down.
2. The path length is $ i + j - 1 $.
3. The collected symbols are exactly those in the cells along the path.
**Objective**
Maximize the number of complete Hackatari logos that can be formed from:
- The infinite supply of $ x $ and $ o $,
- The collected multiset of symbols $ \{>, -, |\} $ from the path.
Let $ n_{>} $, $ n_{-} $, $ n_{|} $ be the counts of $ > $, $ - $, $ | $ collected along a path.
Each logo requires exactly one of each: $ > $, $ - $, $ | $.
Thus, the number of logos formable along a path is:
$$
\min(n_{>}, n_{-}, n_{|})
$$
Find:
$$
\max_{\text{all valid paths from } (1,1)} \left( \min(n_{>}, n_{-}, n_{|}) \right)
$$