CUBE-T199: Sagittarius A*

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef tuple<int, int, int, int> tpp;

const int N = 1e5;

vector<tpp> edges;
vector<int> chosen;
int ds[N + 1], sz[N + 1];

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edges.emplace_back(w, u, v, i);
    }
    sort(edges.begin(), edges.end(), greater<tpp>());

    for(int i = 1; i <= nVertex; ++i){
        ds[i] = i;
        sz[i] = 1;
    }

    lli sum = 0;
    bool lastOne = false;
    for(tpp e : edges){
        int w = get<0>(e);
        int u = get<1>(e);
        int v = get<2>(e);
        int i = get<3>(e);
        u = dsFind(u);
        v = dsFind(v);
        if(u != v){
            sum += w;
            if(sz[u] < sz[v]){
                swap(u, v);
            }
            ds[v] = u;
            sz[u] += sz[v];
            chosen.push_back(i);
        } else if(!lastOne){
            sum += w;
            lastOne = true;
            chosen.push_back(i);
        }
    }

    bool connected = true;
    for(int i = 1; i < nVertex; ++i){
        if(dsFind(i) != dsFind(i + 1)){
            connected = false;
            break;
        }
    }
    if(!connected || !lastOne){
        cout << "-1";
        return 0;
    }

    int cmd;
    scanf("%d", &cmd);
    cout << sum << '\n';
    if(cmd == 2){
        for(int x : chosen){
            cout << x << ' ';
        }
    }

    return 0;
}