## 并查集

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://www.luogu.com.cn/problem/P3367

n, m = map(int, input().split()) p = list(range(n + 1)) r = [1] * (n + 1) def find(x): if (p[x] == x): return x p[x] = find(p[x]) return p[x] def union(x, y): x = find(x) y = find(y) if (x == y): return if (r[x] == r[y]): r[y] += 1 elif (r[y] < r[x]): x, y = y, x p[x] = y for i in range(0, m): cmd, x, y = map(int, input().split()) if (cmd == 1): union(x, y) else: print('Y' if find(x) == find(y) else 'N')

## Kruskal 最小生成树

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

https://www.luogu.com.cn/problem/P3366

def find(x): if (p[x] == x): return x p[x] = find(p[x]) return p[x] def union(x, y): # x = find(x) # y = find(y) if (x == y): return if (r[x] == r[y]): r[y] += 1 elif (r[y] < r[x]): x, y = y, x p[x] = y n, m = map(int, input().split()) p = list(range(n + 1)) r = [1] * (n + 1) edges = [] for i in range(m): edges.append(list(map(int, input().split()))) edges.sort(key=lambda e:e[2]) mst = 0 for e in edges: x = find(e[0]) y = find(e[1]) if x != y: union(x, y) mst += e[2] print(mst)