p323.ans1
======================
5 2 1
4

=================
p323.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;
    }
};

using Edge = tuple<int, int, int, int, int>;

int n, m, k;
vector<Edge> edges;
vector<vector<pair<int, int>>> airlines;

void read() {
    cin >> n >> m >> k;
    edges.resize(k);
    airlines.assign(m, {});
    int idx = 0;
    for(auto& [p, c, u, v, i]: edges) {
        cin >> u >> v >> c >> p;
        i = idx++;
        u--;
        v--;
        c--;

        airlines[c].push_back({u, v});
    }
}

void solve() {
    // We must pick one airline to survive and buy enough other flights (each
    // at its tax cost) so the survivor's set of flights connects all towns.
    // For a fixed surviving airline this is a minimum spanning forest problem:
    // start with the survivor's own flights already contracted (cost 0), then
    // add the cheapest remaining flights to finish connecting everything.
    //
    // Key reduction: the only flights ever worth buying belong to the global
    // minimum spanning tree built over all flights by tax. Any non-MST edge
    // can always be replaced by a cheaper MST path, so we first Kruskal over
    // all K edges to keep just the n-1 relevant tree edges.
    //
    // Then for each candidate airline we run a DSU pre-seeded with that
    // airline's free flights and Kruskal over the relevant edges (already
    // sorted by tax), summing the bought taxes and recording their indices.
    // We take the airline giving the minimum total cost.

    sort(edges.begin(), edges.end());

    DSU global_mst(n);
    vector<Edge> relevant;
    for(auto [p, c, u, v, i]: edges) {
        if(!global_mst.connected(u, v)) {
            global_mst.unite(u, v);
            relevant.push_back({p, c, u, v, i});
        }
    }

    int64_t best_cost = LLONG_MAX;
    int best_airline = -1;
    vector<int> best_purchases;

    for(int airline_to_keep = 0; airline_to_keep < m; airline_to_keep++) {
        DSU d(n);
        for(auto [u, v]: airlines[airline_to_keep]) {
            d.unite(u, v);
        }

        int64_t curr_ans = 0;
        vector<int> purchases;
        for(auto [p, c, u, v, i]: relevant) {
            if(!d.connected(u, v)) {
                d.unite(u, v);
                curr_ans += p;
                purchases.push_back(i + 1);
            }
        }

        if(curr_ans < best_cost) {
            best_cost = curr_ans;
            best_airline = airline_to_keep;
            best_purchases = purchases;
        }
    }

    cout << best_cost << ' ' << best_airline + 1 << ' ' << best_purchases.size()
         << '\n';
    for(int idx: best_purchases) {
        cout << idx << '\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();
        solve();
    }

    return 0;
}

=================
p323.in1
======================
4 3 4
2 3 1 6
4 3 2 7
1 2 2 3
1 3 3 5

=================
statement.txt
======================
323. Aviamachinations
Time limit per test: 2.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berland consists of N towns as you probably already know. Berland also has M domestic airlines. In fact all these airlines belong to Don Berlione. Don Berlione was forced to create a number of companies instead of just one by the Antimonopoly Committee.

The Antimonopoly Committee was disbanded as a result of a government crisis. So, Don Berlione decided to close all but one airline. Naturally, this company should have flights (possibly including stopovers) from any town of Berland to any other one. To be able to choose the airline satisfying the above requirement, Don Berlione decided to carry out a number of fake purchase-sell operations. During a purchase-sell operation a flight of one airline is passed under the control of another airline. A purchase-sell operation is just a money transfer from one pocket to another. But still a special tax should be paid to the government for each operation.

So each flight is characterized by two towns it connects, the airline it belongs to and the tax amount that should be paid for a purchase-sell operation.

Your task is to find P — the minimum possible amount of money Don Berlione needs to spend to make it possible to leave only one airline carrying out flights (possibly with stopovers) from each town of Berland to any other. Also you need to suggest a plan of actions for Don Berlione.

Input
The first line of the input file contains three integer numbers N, M, K (1 ≤ N ≤ 2000; 1 ≤ M ≤ 2000; 0 ≤ K ≤ 200000), where N is the number of towns, M is the number of airlines, K is the number of flights. Each of the following K lines contains the description of the flight given by four integer numbers ai, bi, ci, pi, where ai, bi (ai != bi; 1≤ ai, bi≤ N) are the numbers of towns connected by the flight (towns are numbered from 1 to N), ci (1≤ ci≤ M) is the number of the airline owning the flight (airlines are numbered from 1 to M), pi (1≤ pi≤ 100000) is the tax amount required for the purchase-sell operation of the flight. Originally all flights are planned in such a way that it is possible to get from each town to any other using flights of one or several airlines. There can be several flights between a pair of towns.

Output
Write the desired minimum amount of money P to the first line of the output. After that write a pair of numbers R and Q to the same line, where R is the index of an airline which should be chosen by Don and Q is the number of purchase-sell operations. Write the description of operations to the following Q lines. Each operation should be characterized by a single integer number idxj, which means that the flight idxj should be sold to the company R. If there are several solutions for the problem, choose any of them.

Example(s)
sample input
sample output
4 3 4
2 3 1 6
4 3 2 7
1 2 2 3
1 3 3 5
5 2 1
4

=================
