{"raw_statement":[{"iden":"statement","content":"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. \n\nThe 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.\n\nWhen 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.\n\nThe 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.\n\nPrint 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.\n\nYou may print any solution if there are many of them. \n\nIn 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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. "},{"iden":"examples","content":"Input410 20 5 320 11 5 210 11 7 11 2 1 1Output52 3 1 4 "},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of wires.  \nFor each wire $ i \\in \\{1, \\dots, n\\} $, define:  \n- $ a_i, b_i \\in \\mathbb{Z}^+ $: endpoints (nodes) to be connected, $ a_i \\ne b_i $,  \n- $ r_i \\in \\mathbb{Z}^+ $: reliability,  \n- $ p_i \\in \\mathbb{Z}^+ $: cost.  \n\nLet $ G = (V, E) $ be a dynamic graph, where $ V $ is the set of all node identifiers appearing in $ \\{a_i, b_i\\} $, and $ E $ is the multiset of wires added incrementally.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 30000 $  \n2. $ 1 \\le a_i, b_i, r_i, p_i \\le 10^9 $  \n3. For each wire $ i $, the edge $ (a_i, b_i) $ is undirected.  \n4. The soldering process is sequential: wires are added one-by-one in an order $ \\sigma \\in S_n $.  \n5. After adding wire $ i $, if a cycle is formed, the **least reliable** wire in the cycle is removed; if multiple such wires exist, the **earliest soldered** one is removed.  \n6. The final graph must be acyclic (i.e., a forest).  \n\n**Objective**  \nFind a permutation $ \\sigma = (\\sigma_1, \\sigma_2, \\dots, \\sigma_n) $ of $ \\{1, \\dots, n\\} $ such that the total cost of wires remaining in the final forest is **maximized**:  \n$$\n\\max_{\\sigma \\in S_n} \\sum_{i \\in \\text{final\\_edges}} p_i\n$$  \nOutput the maximum total cost and any such optimal order $ \\sigma $.","simple_statement":"Vasya must solder n wires one by one. Each wire connects two points (a_i, b_i), has reliability r_i and cost p_i.  \n\nIf adding a wire creates a cycle, the least reliable wire in the cycle breaks (and is removed). If there’s a tie in reliability, the earliest-soldered one breaks.  \n\nGoal: Choose the soldering order to maximize the total cost of wires that remain after all are processed.  \n\nOutput:  \n- Maximum total cost  \n- The order of wire indices (1-based) to achieve it  \n\nYou may output any valid order.","has_page_source":false}