СНМ

mail@pastecode.io avatar
unknown
plain_text
2 years ago
758 B
3
Indexable
Never
#include <bits/stdc++.h>

#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair

using namespace std;

const int N = 1e5 + 123;

int n, m;

int p[N], sum[N];

set <int,pii> s;

int get (int v) {
    if (p[v] == v)return v;
    return p[v] = (get p[v]);
}

void make_union (int v, int u, int w) {
    u = get (u);
    v = get (v);
    p[v] = u;
    sum[u] += sum[v] + w;
}

int main () {
    cin >> n >> m;
    for (int i = 1;i <= m;i ++) {
        int l, r, x;
        cin >> l >> r >> x;
        s.mp (x, mp (l, r));
    }
    for (auto it : s) {
        pair <int,pii> pr;
        int w = pr.F, v = pr.S.F, u = pr.S.S;
        if (get (v) != get (u)) {
            make_union (v, u, w);
        }
    }
    cout << sum[get (1)];
}