#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int get(const int &n, int *&subtree) {
if (subtree[n] == n) return n;
return subtree[n] = get(subtree[n], subtree);
}
void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) {
int ra = get(a, subtree), rb = get(b, subtree);
if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb;
else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra;
else {
subtree[ra] = rb;
vertex_rank[rb]++;
}
}
int main()
{
int vertices, edges; // vertices <= edges : Граф является связным.
scanf("%i%i", &vertices, &edges);
vector <pair<int, pair<int, int>>> v(edges);
for (int i = 0; i < edges; ++i) {
scanf("%i", &v[i].second.first); // vertex out
scanf("%i", &v[i].second.second); // vertex in
scanf("%i", &v[i].first); // weight
}
sort(v.begin(), v.end());
int *subtree = new int[vertices];
int *vertex_rank = new int[vertices];
for (int i = 0; i < vertices; i++) {
subtree[i] = i;
vertex_rank[i] = 1;
}
int spanning_tree_weight = 0;
for (int i = 0; i < edges; ++i) {
if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) {
spanning_tree_weight += v[i].first;
merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank);
}
}
printf("%i", spanning_tree_weight);
delete[] subtree;
delete[] vertex_rank;
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx1dGlsaXR5Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGdldChjb25zdCBpbnQgJm4sIGludCAqJnN1YnRyZWUpIHsKCWlmIChzdWJ0cmVlW25dID09IG4pIHJldHVybiBuOwoJcmV0dXJuIHN1YnRyZWVbbl0gPSBnZXQoc3VidHJlZVtuXSwgc3VidHJlZSk7ICAKfQoKdm9pZCBtZXJnZShjb25zdCBpbnQgJmEsIGNvbnN0IGludCAmYiwgaW50IComc3VidHJlZSwgaW50IComdmVydGV4X3JhbmspIHsKCWludCByYSA9IGdldChhLCBzdWJ0cmVlKSwgcmIgPSBnZXQoYiwgc3VidHJlZSk7CglpZiAodmVydGV4X3JhbmtbcmFdIDwgdmVydGV4X3JhbmtbcmJdKSBzdWJ0cmVlW3JhXSA9IHJiOwoJZWxzZSBpZiAodmVydGV4X3JhbmtbcmJdIDwgdmVydGV4X3JhbmtbcmFdKSBzdWJ0cmVlW3JiXSA9IHJhOwoJZWxzZSB7CgkJc3VidHJlZVtyYV0gPSByYjsKCQl2ZXJ0ZXhfcmFua1tyYl0rKzsKCX0KfQoKaW50IG1haW4oKQp7CglpbnQgdmVydGljZXMsIGVkZ2VzOyAvLyB2ZXJ0aWNlcyA8PSBlZGdlcyA6INCT0YDQsNGEINGP0LLQu9GP0LXRgtGB0Y8g0YHQstGP0LfQvdGL0LwuCglzY2FuZigiJWklaSIsICZ2ZXJ0aWNlcywgJmVkZ2VzKTsKCXZlY3RvciA8cGFpcjxpbnQsIHBhaXI8aW50LCBpbnQ+Pj4gdihlZGdlcyk7Cglmb3IgKGludCBpID0gMDsgaSA8IGVkZ2VzOyArK2kpIHsKCQlzY2FuZigiJWkiLCAmdltpXS5zZWNvbmQuZmlyc3QpOyAvLyB2ZXJ0ZXggb3V0CgkJc2NhbmYoIiVpIiwgJnZbaV0uc2Vjb25kLnNlY29uZCk7IC8vIHZlcnRleCBpbgoJCXNjYW5mKCIlaSIsICZ2W2ldLmZpcnN0KTsgLy8gd2VpZ2h0Cgl9Cglzb3J0KHYuYmVnaW4oKSwgdi5lbmQoKSk7CglpbnQgKnN1YnRyZWUgPSBuZXcgaW50W3ZlcnRpY2VzXTsKCWludCAqdmVydGV4X3JhbmsgPSBuZXcgaW50W3ZlcnRpY2VzXTsKCWZvciAoaW50IGkgPSAwOyBpIDwgdmVydGljZXM7IGkrKykgewoJCXN1YnRyZWVbaV0gPSBpOwoJCXZlcnRleF9yYW5rW2ldID0gMTsKCX0KCWludCBzcGFubmluZ190cmVlX3dlaWdodCA9IDA7Cglmb3IgKGludCBpID0gMDsgaSA8IGVkZ2VzOyArK2kpIHsKCQlpZiAoZ2V0KHZbaV0uc2Vjb25kLmZpcnN0IC0gMSwgc3VidHJlZSkgIT0gZ2V0KHZbaV0uc2Vjb25kLnNlY29uZCAtIDEsIHN1YnRyZWUpKSB7CgkJCXNwYW5uaW5nX3RyZWVfd2VpZ2h0ICs9IHZbaV0uZmlyc3Q7CgkJCW1lcmdlKHZbaV0uc2Vjb25kLmZpcnN0IC0gMSwgdltpXS5zZWNvbmQuc2Vjb25kIC0gMSwgc3VidHJlZSwgdmVydGV4X3JhbmspOwoJCX0KCX0KCXByaW50ZigiJWkiLCBzcGFubmluZ190cmVlX3dlaWdodCk7CglkZWxldGVbXSBzdWJ0cmVlOwoJZGVsZXRlW10gdmVydGV4X3Jhbms7CglyZXR1cm4gMDsKfQ==