## 1. Abridged problem statement

You are given **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 one by one.

Whenever adding a wire creates a **cycle**, then **exactly one wire in that cycle burns out and disappears**:
- the wire with **minimum reliability** in the cycle burns;
- if there are multiple with the same minimum reliability, the one that was **soldered earlier** burns.

After burning, the graph becomes acyclic again.

Goal: choose an order maximizing the **sum of costs of wires remaining at the end**, and output that maximum sum and any achieving order.

Constraints: \(1 \le n \le 30000\), values up to \(10^9\), multiple edges allowed.

---

## 2. Detailed editorial

### Key observation: the final set of remaining wires is a "maximum-reliability forest" with a special tie-break
The process maintains a forest (acyclic) after each step because cycles are immediately broken by burning one edge.

Consider what happens when you add an edge \(e\) between two vertices already connected: it forms a unique cycle. Burning removes the **weakest** edge (smallest reliability) on that cycle; if reliabilities tie, it removes the one soldered **earliest**.

This is exactly the same rule that makes **Kruskal's algorithm** correct for building a **maximum spanning forest by reliability**. Here we want to *keep* edges with **higher reliability**; any time a cycle appears, the minimum-reliability edge in that cycle is discarded — so the structure evolves toward a maximum-by-reliability forest.

The only subtlety is the tie-break among equal reliabilities: *earlier soldered burns first*, meaning **later soldered edges of the same reliability are favored to stay**.

So, informally:
- Primarily, the final forest is determined by **reliability** (keep higher \(r\)).
- Among equal \(r\), the process favors keeping edges that appear **later** in the soldering order.

### Reformulating the goal
We want the final forest (under these rules) to have **maximum total cost** \(\sum p\).

The reliabilities dictate which edges can survive: among edges with higher reliability, they tend to be kept over lower reliability. The only freedom we have is within **equal reliability groups** via the "burn earlier" tie-break: we can arrange order so that among same \(r\), the set that survives is biased toward edges soldered later.

To maximize final cost, for equal reliability \(r\), we want **higher-cost edges to be soldered later**, so that if ties happen, cheaper ones are the ones more likely to burn.

### Constructing an optimal order
Sort wires by **increasing reliability \(r\)**, breaking ties by **increasing cost \(p\)**. So within the same \(r\), cheap edges come first, expensive ones last. Call this sorted list `perm`.

### Reverse Kruskal idea
To compute the final kept set without simulating burning online, traverse edges **from the end of the sorted order to the beginning**, and greedily keep edges that connect two different DSU components. This reconstructs exactly the set of edges that will remain.

Why? Traversing from the end means we first consider:
- higher reliability edges (because \(r\) increasing forward ⇒ decreasing backward),
- and among equal \(r\), higher cost edges first (since \(p\) increasing forward ⇒ decreasing backward).

Adding an edge only if it connects two components builds a forest maximizing "priority" lexicographically by \((r, p)\), which matches the burn rule preferences: when a cycle happens, the least reliable (and among ties the earliest) is removed, so the survivors are exactly those chosen by this reverse greedy inclusion.

Concretely:
- Let `perm` be indices sorted by (r asc, p asc).
- Initialize DSU on all vertices.
- Iterate `i = n-1 ... 0`:
  - let `idx = perm[i]`
  - if its endpoints are in different DSU components: keep it (union) and add its cost to answer.

The resulting chosen edges are the final surviving wires, and the order `perm` is the optimal soldering order.

### Correctness sketch
1. **Reliability optimality**: The burn rule always removes a minimum-reliability edge on a created cycle, so no final forest can "prefer" a lower reliability edge over a higher reliability alternative — same exchange argument as Kruskal.
2. **Tie handling**: If reliabilities tie on the weakest edges in a cycle, the earliest burns. Therefore, to maximize the chance that an edge survives among equal \(r\), place it later; sorting by \(p\) ascending within equal \(r\) makes higher-cost edges later.
3. **Reverse greedy reconstruction**: The set of survivors for this order is exactly what you get by scanning edges backward and building a forest.

### Complexity
- Coordinate-compress vertex labels (because \(a_i, b_i\) up to \(10^9\)): \(O(n \log n)\).
- Sort edges: \(O(n \log n)\).
- DSU operations: \(O(n \alpha(n))\).

---

## 3. 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;
}
```

---

## 4. 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()
```

---

## 5. Compressed editorial

Sort wires by \((r \uparrow, p \uparrow)\) and output this order. The burn rule always removes the minimum-reliability edge on any formed cycle; among equal reliabilities it removes the earliest, so placing higher-cost edges later within equal \(r\) makes them more likely to survive.

To compute the final maximum total cost for this order, run "reverse Kruskal": traverse the sorted list from back to front and add an edge iff it connects two different DSU components. Sum costs of added edges; that sum is maximal achievable. Coordinate-compress endpoint labels. Complexity \(O(n \log n)\).
