文件目录

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int f[105][105], fat[105], n, m, x, y, w;
bool vis[105];
int ans;
struct node
{
    int to, w;
    bool operator<(const node &b) const
    {
        return w > b.w;
    }
};
void prim()
{
    priority_queue<node> p;
    p.push({1, 0});
    while (!p.empty())
    {
        node u = p.top();
        p.pop();
        if (vis[u.to])
            continue;
        vis[u.to] = true;
        if (fat[u.to] != u.to)
            ans -= f[fat[u.to]][u.to];
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && f[u.to][i] != f[0][0])
            {
                p.push({i, f[u.to][i]});
                if (f[u.to][i] < f[fat[i]][i])
                    fat[i] = u.to;
            }
        }
    }
}
int main()
{
    memset(f, 0x3f, sizeof(f));
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> w;
        ans += w;
        if (w == 0)
            f[x][y] = f[y][x] = f[0][0];
        else
            f[x][y] = f[y][x] = w;
    }
    for (int i = 1; i <= n; i++)
        fat[i] = i;
    prim();
    cout << ans;
    return 0;
}