<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

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 ≠q 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.

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.

<|response|>
## 1. Abridged problem statement

You have `n` wires. Wire `i` connects places `a_i` and `b_i`, has reliability `r_i` and cost `p_i`. You must choose an order to solder all wires.

After soldering a wire, if the current scheme contains a **cycle**, then **exactly one** wire in that cycle burns and is removed:
- the wire with **minimum reliability** burns;
- if there are several with the same minimum reliability, the one soldered **earlier** burns.

After burning, the scheme becomes acyclic again.

Goal: choose a soldering order maximizing the **total cost of wires remaining at the end**, and output that maximum cost and any optimal order.

Constraints: `n ≤ 30000`, endpoints up to `1e9`, multiple edges possible.

---

## 2. Key observations

1. **The scheme is always a forest after each step.**
   Any time a cycle appears, one edge is removed immediately, restoring acyclicity.

2. **When a cycle forms, the "worst" edge in that cycle is removed** where "worst" means:
   - smaller `r` is worse,
   - if `r` ties, **earlier soldered is worse** (because earlier burns).

3. This behavior matches the well-known **cycle property** behind spanning forests:
   In any cycle, an edge that is minimal by the chosen priority cannot be part of the best final forest; it will be eliminated when a cycle arises.

4. Therefore, the final set of surviving edges is a **maximum spanning forest by reliability**, with a special tie-break: among equal reliability edges, **later soldered edges are preferred to survive**.

5. To maximize final total cost, within the same reliability `r`, we want **expensive edges to be soldered later**, so that if equal-`r` edges compete in a cycle, cheaper ones are more likely to burn.

---

## 3. Full solution approach

### Step A: Choose an order to solder
Sort wires by:
1. `r` increasing,
2. `p` increasing.

Call this sorted list `perm` (it is also the order we will output).

Why this order?
- Low reliability edges should come earlier because higher reliability edges tend to survive.
- For equal reliability, cheap first / expensive last ensures that if equal-`r` edges compete (tie case), the earlier (cheaper) one burns.

### Step B: Compute the maximum achievable final cost (without simulating burns)
Instead of simulating "add edge → find cycle → remove minimum", use **reverse Kruskal**:

- Traverse `perm` from the end to the beginning (i.e., from "most preferred to survive" to "least preferred").
- Maintain a DSU (Union-Find).
- If an edge connects two different DSU components, **keep it** and add its cost; otherwise skip it.

This builds a forest that is maximum under the priority:
- higher `r` first,
- for equal `r`, higher `p` first (because we are traversing the `p`-ascending order backwards).

That forest is exactly the set of wires that remain after soldering in `perm`.

### Step C: Coordinate compression
Endpoints `a_i, b_i` can be up to `1e9`, but there are at most `2n` distinct places. Compress them to `0..m-1` for DSU.

### Complexity
- Compression: `O(n log n)`
- Sorting: `O(n log n)`
- DSU pass: `O(n α(n))`

---

## 4. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/dsu.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }

    vector<vector<int>> components() {
        vector<vector<int>> comp(n + 1);
        for(int i = 0; i <= n; i++) {
            comp[root(i)].push_back(i);
        }
        return comp;
    }
};

int n;
vector<tuple<int, int, int, int>> wires;

void read() {
    vector<int> nodes;

    cin >> n;
    wires.resize(n);
    for(auto& [u, v, r, p]: wires) {
        cin >> u >> v >> r >> p;
        nodes.push_back(u);
        nodes.push_back(v);
    }

    sort(nodes.begin(), nodes.end());
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    for(auto& [u, v, r, p]: wires) {
        u = lower_bound(nodes.begin(), nodes.end(), u) - nodes.begin();
        v = lower_bound(nodes.begin(), nodes.end(), v) - nodes.begin();
    }
}

void solve() {
    // We can notice that we always will maintain an MST based on the
    // reliability. This means that no matter what order we choose the MST will
    // be almost the same (we can get convinced by correctness of Kruskal) - the
    // only difference comes in how we order the edges of the same reliability.
    // This is also not as hard - we simply want to keep the most expensive ones
    // last (so that previous cheaper wires get deleted). In other words it's
    // enough to sort the wires by "r" first, and then break ties by "p". This
    // is the order we will do and we could simulate the process with some
    // advanced data structures like link-cut trees, but there is an easier way
    // to recover the final configuration and price - we can simply do Kruskal
    // from the back.

    DSU dsu(2 * n);

    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);

    sort(perm.begin(), perm.end(), [&](int i, int j) {
        auto& [u1, v1, r1, p1] = wires[i];
        auto& [u2, v2, r2, p2] = wires[j];
        if(r1 != r2) {
            return r1 < r2;
        }
        return p1 < p2;
    });

    int64_t total_cost = 0;
    for(int i = n - 1; i >= 0; i--) {
        int idx = perm[i];
        auto& [u, v, r, p] = wires[idx];
        if(!dsu.connected(u, v)) {
            dsu.unite(u, v);
            total_cost += p;
        }
    }

    cout << total_cost << "\n";
    for(int i = 0; i < n; i++) {
        if(i > 0) {
            cout << " ";
        }
        cout << perm[i] + 1;
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5. Python Solution

```python
import sys
from bisect import bisect_left

# ---------- DSU (Disjoint Set Union / Union-Find) ----------
class DSU:
    def __init__(self, n: int):
        # We'll use 0..n-1
        self.par = list(range(n))
        self.sz = [1] * n

    def root(self, x: int) -> int:
        # Path compression
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x

    def connected(self, a: int, b: int) -> bool:
        return self.root(a) == self.root(b)

    def unite(self, a: int, b: int) -> None:
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        # Union by size: attach smaller to bigger
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    wires = []
    nodes = []

    # Read wires; store endpoints for coordinate compression
    idx = 1
    for _ in range(n):
        a = int(data[idx]); b = int(data[idx + 1])
        r = int(data[idx + 2]); p = int(data[idx + 3])
        idx += 4
        wires.append([a, b, r, p])
        nodes.append(a)
        nodes.append(b)

    # Coordinate compress node labels to 0..m-1
    nodes = sorted(set(nodes))
    for w in wires:
        w[0] = bisect_left(nodes, w[0])
        w[1] = bisect_left(nodes, w[1])

    m = len(nodes)
    dsu = DSU(m)

    # perm = indices 0..n-1, sorted by (reliability asc, cost asc)
    perm = list(range(n))
    perm.sort(key=lambda i: (wires[i][2], wires[i][3]))

    # Reverse traversal: keep an edge if it connects different components
    total_cost = 0
    for k in range(n - 1, -1, -1):
        i = perm[k]
        u, v, r, p = wires[i]
        if not dsu.connected(u, v):
            dsu.unite(u, v)
            total_cost += p

    # Output
    out = []
    out.append(str(total_cost))
    out.append(" ".join(str(i + 1) for i in perm))
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
```

This outputs the maximal achievable final total cost and a valid optimal soldering order (any optimal order is accepted).
