CUBE-199: Sagittarius A*

#include <bits/stdc++.h>

using namespace std;

using lli = long long;
const lli INF = 2e18;
using pi = pair <int, int>;
using pli = pair <lli, int>;
using P = pair <pli, pi>;

int n,m;
int parent[100010];

int root(int u){
    if(parent[u] == u) return u;
    return parent[u] = root(parent[u]);
}

void mrg(int u, int v){
    u = root(parent[u]);
    v = root(parent[v]);
    parent[u] = v;
}

int main(){

    scanf("%d%d", &n, &m);

    priority_queue <P> pq, keep;

    for(int i=1;i<=m;i++){
        int u, v;
        lli w;
        scanf("%d%d%lld", &u, &v, &w);
        pq.push({ {w, i}, {u, v}});
        parent[u] = u;
        parent[v] = v;
    }
    int t;
    scanf("%d", &t);

    lli d = 0;
    int cnt = 0;
    set <int> line;
    while(pq.size() > 0 and cnt < n){
        int u, v, l;
        lli w;
        w = pq.top().first.first;
        l = pq.top().first.second;
        u = pq.top().second.first;
        v = pq.top().second.second;
        pq.pop();

        if(root(u) == root(v)) {
            keep.push({ {w, l}, {u, v}});
            continue;
        }
        mrg(u, v);

        d += w;
        line.insert(l);
        cnt++;
    }

    while(keep.size() > 0 and cnt < n){
        int u, v, l;
        lli w;
        w = keep.top().first.first;
        l = keep.top().first.second;
        u = keep.top().second.first;
        v = keep.top().second.second;
        keep.pop();
        d += w;
        line.insert(l);
        cnt ++;
    }

    if(cnt != n) {
        printf("-1");
        return 0;
    }

    for(int i=1;i<=n;i++) {
        if(root(parent[i]) != root(parent[1])) {
            printf("-1");
            return 0;
        }
    }

    printf("%lld\n",d);

    if(t == 1)
        return 0;
    for(auto l:line) printf("%d ",l);

    return 0;
}