编辑代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010, INF = 0x3f3f3f3f;
struct Edges
{
    int a, b, w;      
    bool operator < (Edges &tmp) const
    {
        return w < tmp.w;
    }
} e[N];
int p[N];
int n, m;
vector<Edges> T;

int Find(int x)
{
    if (x != p[x]) p[x] = Find(p[x]);
    return p[x];
}

int kruskal()
{
    int res = 0, cnt = 0;
    for (int i = 1; i <= n; i ++) p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; i ++)
    {
        int a = e[i].a, b = e[i].b, w = e[i].w;
        if (Find(a) != Find(b))
        {
            p[Find(a)] = Find(b);
            res += w;
            cnt ++;
            T.push_back(e[i]);
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++)
        cin >> e[i].a >> e[i].b >> e[i].w;

    cout << endl;

    int res = kruskal();

    if (res == INF) cout << "impossible";
    else
    {
        cout << "Sum of W: " << res << endl << endl;
        for (int i = 0; i < T.size(); i ++)
            cout << T[i].a << " " << T[i].b << " " << T[i].w << endl;
    }

    return 0;
}