Find the sum of weights of edges of the Minimum Spanning Tree for a given weighted undirected graph G = (V, E).

Constraints

* 1 ≤ |V| ≤ 10,000
* 0 ≤ |E| ≤ 100,000
* 0 ≤ wi ≤ 10,000
* The graph is connected
* There are no parallel edges
* There are no self-loops

Input


|V| |E|
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1


, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target verticess of i-th edge (undirected) and wi represents the weight of the i-th edge.

Output

Print the sum of the weights of the Minimum Spanning Tree.

Examples

Input

4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5


Output

3


Input

6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6


Output

5

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
class Kruskal_UnionFind:

	def __init__(self, N):
		self.edges = []
		self.rank = [0] * N
		self.par = [i for i in range(N)]
		self.counter = [1] * N

	def add(self, u, v, d):
		self.edges.append([u, v, d])

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			z = self.counter[x] + self.counter[y]
			(self.counter[x], self.counter[y]) = (z, z)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def size(self, x):
		x = self.find(x)
		return self.counter[x]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def Kruskal(self):
		edges = sorted(self.edges, key=lambda x: x[2])
		res = 0
		for e in edges:
			if not self.same(e[0], e[1]):
				self.unite(e[0], e[1])
				res += e[2]
		return res
(V, E) = map(int, input().split())
graph = Kruskal_UnionFind(V)
for i in range(E):
	(s, t, w) = map(int, input().split())
	graph.add(s, t, w)
print(graph.Kruskal())


import sys
from itertools import islice

def kruskal(v_count: int, edges: list) -> int:
	tree = [-1] * v_count

	def get_root(x):
		if tree[x] < 0:
			return x
		tree[x] = get_root(tree[x])
		return tree[x]

	def unite(a):
		(x, y) = (get_root(a[1]), get_root(a[2]))
		if x != y:
			(big, small) = (x, y) if tree[x] < tree[y] else (y, x)
			tree[big] += tree[small]
			tree[small] = big
		return x != y
	cost = 0
	for (w, _s, _t) in islice(filter(unite, sorted(edges)), v_count - 1):
		cost += w
	return cost
(V, E) = map(int, input().split())
edges = [(w, s, t) for (s, t, w) in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))


import heapq

def set_heapq(que, edge, used, v, add_dist=0):
	for (a, b) in edge[v]:
		if used[b]:
			heapq.heappush(que, (a + add_dist, b))
	return que

def prim_heap(edge, n):
	used = [True] * n
	edgelist = []
	edgelist = set_heapq(edgelist, edge, used, 0)
	used[0] = False
	res = 0
	while len(edgelist) != 0:
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		edgelist = set_heapq(edgelist, edge, used, v)
		res += minedge[0]
	return res
(V, E) = map(int, input().split())
edge = [[] for _ in range(V)]
for i in range(E):
	(s, t, w) = map(int, input().split())
	edge[s].append((w, t))
	edge[t].append((w, s))
print(prim_heap(edge, V))


import heapq
H = []
(V, E) = map(int, input().split())
for _ in range(E):
	(s, t, w) = map(int, input().split())
	heapq.heappush(H, (w, s, t))

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n

	def root(self, a):
		if self.parent[a] < 0:
			return a
		else:
			self.parent[a] = self.root(self.parent[a])
			return self.parent[a]

	def size(self, a):
		return -self.parent[self.root(a)]

	def connect(self, a, b) -> bool:
		a = self.root(a)
		b = self.root(b)
		if a == b:
			return False
		if self.size(a) < self.size(b):
			(a, b) = (b, a)
		self.parent[a] += self.parent[b]
		self.parent[b] = a
		return True
unif = UnionFind(V)
ans = 0
while len(H) > 0:
	(w, s, t) = heapq.heappop(H)
	if unif.root(s) == unif.root(t):
		continue
	unif.connect(s, t)
	ans += w
print(ans)


(v, e) = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key=lambda x: x[2])
group = [[i] for i in range(v)]
key = [i for i in range(v)]
sum = 0
for (i, j, k) in adj:
	if key[i] != key[j]:
		h = key[j]
		group[key[i]] += group[h]
		sum += k
		for t in group[h]:
			key[t] = key[i]
		group[h] = []
		if len(group[key[i]]) == v:
			break
print(sum)


class Kruskal_UnionFind:

	def __init__(self, N):
		self.edges = []
		self.rank = [0] * N
		self.par = [i for i in range(N)]
		self.counter = [1] * N

	def add(self, u, v, d):
		self.edges.append([u, v, d])

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			z = self.counter[x] + self.counter[y]
			(self.counter[x], self.counter[y]) = (z, z)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def size(self, x):
		x = self.find(x)
		return self.counter[x]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def Kruskal(self):
		edges = sorted(self.edges, key=lambda x: x[2])
		res = 0
		for e in edges:
			if not self.same(e[0], e[1]):
				self.unite(e[0], e[1])
				res += e[2]
		return res
(V, E) = map(int, input().split())
Krus = Kruskal_UnionFind(V)
for _ in range(E):
	(s, t, w) = map(int, input().split())
	Krus.add(s, t, w)
ans = Krus.Kruskal()
print(ans)


import array
import collections
Edge = collections.namedtuple('Edge', 'start end weight')

class UnionFind(object):

	def __init__(self, number_of_nodes):
		self.par = array.array('L', range(number_of_nodes))
		self.rank = array.array('L', (0 for i in range(number_of_nodes)))

	def root(self, node):
		if self.par[node] == node:
			return node
		else:
			r = self.root(self.par[node])
			self.par[node] = r
			return r

	def in_the_same_set(self, node1, node2):
		return self.root(node1) == self.root(node2)

	def unite(self, node1, node2):
		x = self.root(node1)
		y = self.root(node2)
		if x == y:
			pass
		elif self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

def compute_mst_kruskal(max_v, edges):
	edges.sort(key=lambda edge: edge.weight)
	uf = UnionFind(max_v)
	mst = []
	for edge in edges:
		if not uf.in_the_same_set(edge.start, edge.end):
			uf.unite(edge.start, edge.end)
			mst.append(edge)
	return mst

def main():
	(max_v, max_e) = map(int, input().split())
	edges = [Edge(*map(int, input().split())) for _ in range(max_e)]
	mst = compute_mst_kruskal(max_v, edges)
	print(sum((edge.weight for edge in mst)))
main()


import array
import collections
import heapq
AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
MAX_INT = 2147483647
NO_V = -1

def compute_mst_prim(v, adj_list):
	pred = collections.defaultdict(lambda : NO_V)
	key = collections.defaultdict(lambda : MAX_INT)
	key[0] = 0
	pq = [(key[i], i) for i in range(v)]
	heapq.heapify(pq)
	in_pq = array.array('B', (True for tmp in range(v)))
	while pq:
		(tmp, u) = heapq.heappop(pq)
		in_pq[u] = False
		for (i, cost) in adj_list[u]:
			if in_pq[i]:
				weight = cost
				if weight < key[i]:
					pred[i] = u
					key[i] = weight
					heapq.heappush(pq, (weight, i))
					in_pq[i] = True
	return (pred, key)
(v, e) = map(int, input().split())
a_list = collections.defaultdict(set)
for _ in range(e):
	(s, t, w) = map(int, input().split())
	a_list[s].add(AdjacentVertex(t, w))
	a_list[t].add(AdjacentVertex(s, w))
(tmp, key) = compute_mst_prim(v, a_list)
print(sum(key.values()))


def find(x):
	global uf
	if uf[x] < 0:
		return x
	else:
		uf[x] = find(uf[x])
		return uf[x]

def union(x, y):
	global uf
	(x, y) = (find(x), find(y))
	if x == y:
		return False
	else:
		if uf[x] < uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
		return True
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	edges.append(tuple(map(int, input().split())))
uf = [-1] * V
mst = []
for e in sorted(edges, key=lambda x: x[2]):
	if find(e[0]) != find(e[1]):
		union(e[0], e[1])
		mst.append(e)
print(sum(map(lambda x: x[2], mst)))


import heapq

class UnionFind:
	from collections import deque

	def __init__(self, v):
		self.v = v
		self._tree = list(range(v + 1))

	def _root(self, a):
		queue = self.deque()
		while self._tree[a] != a:
			queue.append(a)
			a = self._tree[a]
		while queue:
			index = queue.popleft()
			self._tree[index] = a
		return a

	def union(self, a, b):
		root_a = self._root(a)
		root_b = self._root(b)
		self._tree[root_b] = root_a

	def find(self, a, b):
		return self._root(a) == self._root(b)
(V, E) = map(int, input().split(' '))
heap = []
for _ in range(E):
	(s, t, w) = map(int, input().split(' '))
	heapq.heappush(heap, (w, s, t))
uf = UnionFind(V)
cost = 0
while heap:
	(w, s, t) = heapq.heappop(heap)
	if not uf.find(s, t):
		uf.union(s, t)
		cost += w
print(cost)


import sys
import heapq as hp
(WHITE, GRAY, BLACK) = (0, 1, 2)

def generate_adj_table(v_table):
	for each in v_table:
		(v_from, v_to, edge_weight) = map(int, each)
		init_adj_table[v_from][v_to] = edge_weight
		init_adj_table[v_to][v_from] = edge_weight
	return init_adj_table

def prim_span_tree():
	distance[init_v] = 0
	parent[init_v] = -1
	path_heap = []
	hp.heappush(path_heap, (0, init_v))
	while len(path_heap) >= 1:
		current_vertex = hp.heappop(path_heap)[1]
		color[current_vertex] = BLACK
		for (adj_vertex, adj_weight) in adj_table[current_vertex].items():
			if color[adj_vertex] is not BLACK:
				if adj_weight < distance[adj_vertex]:
					distance[adj_vertex] = adj_weight
					parent[adj_vertex] = current_vertex
					color[adj_vertex] = GRAY
					hp.heappush(path_heap, (adj_weight, adj_vertex))
	return distance
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
parent = [-1] * vertices
distance = [float('inf')] * vertices
color = [WHITE] * vertices
init_v = 0
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
print(sum(prim_span_tree()))


class Kruskal_UnionFind:

	def __init__(self, N):
		self.edges = []
		self.rank = [0] * N
		self.par = [i for i in range(N)]
		self.counter = [1] * N

	def add(self, u, v, d):
		self.edges.append([u, v, d])

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			z = self.counter[x] + self.counter[y]
			(self.counter[x], self.counter[y]) = (z, z)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def size(self, x):
		x = self.find(x)
		return self.counter[x]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def Kruskal(self):
		edges = sorted(self.edges, key=lambda x: x[2])
		res = 0
		for e in edges:
			if not self.same(e[0], e[1]):
				self.unite(e[0], e[1])
				res += e[2]
		return res
(v, e) = map(int, input().split())
stw = [list(map(int, input().split())) for _ in range(e)]
T = Kruskal_UnionFind(v)
for i in range(e):
	s = stw[i][0] - 1
	t = stw[i][1] - 1
	w = stw[i][2]
	T.add(s, t, w)
print(T.Kruskal())


from heapq import heappop, heappush
from typing import List, Tuple

def find(x):
	global parents
	if x == parents[x]:
		return x
	else:
		tmp = find(parents[x])
		parents[x] = tmp
		return tmp
(V, E) = map(int, input().split())
parents = [i for i in range(V)]
que: List[Tuple[int, int, int]] = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	heappush(que, (w, s, t))
ans = 0
while que:
	(w, s, t) = heappop(que)
	root_s = find(s)
	root_t = find(t)
	if root_s != root_t:
		parents[root_s] = root_t
		ans += w
print(ans)


import sys
import itertools
import time
import math
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind(object):

	def __init__(self, n=1):
		self.link = [i for i in range(n)]
		self.size = [1 for _ in range(n)]

	def find(self, x):
		if self.link[x] == x:
			return x
		self.link[x] = self.find(self.link[x])
		return self.link[x]

	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.link[y] = x
		self.size[x] += self.size[y]

	def get_size(self, x):
		x = self.find(x)
		return self.size[x]
(V, E) = map(int, input().split())
edges = [0] * E
for i in range(E):
	(s, t, w) = map(int, input().split())
	edges[i] = (w, s, t)
u = UnionFind(V)
edges = sorted(edges)
ans = 0
for e in edges:
	(w, s, t) = e
	if u.is_same(s, t):
		continue
	u.unite(s, t)
	ans += w
print(ans)


INF = 2000000000

class Node:

	def __init__(self, num):
		self.num = num
		self.parent = self
		self.rank = 0

def findSet(node):
	tmp = []
	while node.parent != node:
		tmp.append(node)
		node = node.parent
	while tmp:
		tmp.pop().parent = node
	return node

def unite(x, y):
	node1 = findSet(nodes[x])
	node2 = findSet(nodes[y])
	if node1.rank == node2.rank:
		node2.parent = node1
		node1.rank += 1
	elif node1.rank > node2.rank:
		node2.parent = node1
	else:
		node1.parent = node2

def same(x, y):
	node1 = findSet(nodes[x])
	node2 = findSet(nodes[y])
	return node1.parent == node2.parent

class Edge:

	def __init__(self, source, target, cost):
		self.source = source
		self.target = target
		self.cost = cost

def kruskal():
	edges.sort(key=lambda u: u.cost)
	for i in range(e):
		if findSet(edges[i].source) != findSet(edges[i].target):
			unite(edges[i].source.num, edges[i].target.num)
			K.append(edges[i])
	total = 0
	for tmp in K:
		total += tmp.cost
	print(total)
nums = list(map(int, input().split()))
n = nums[0]
e = nums[1]
edges = []
nodes = []
for i in range(n):
	nodes.append(Node(i))
for i in range(e):
	nums = list(map(int, input().split()))
	tmp = Edge(nodes[nums[0]], nodes[nums[1]], nums[2])
	edges.append(tmp)
K = []
kruskal()


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
(V, E) = map(int, input().split())
nodes = sorted([list(map(int, input().split())) for _ in range(E)], key=lambda x: x[2])
a = UnionFind(V)
ans = 0
for node in nodes:
	(si, ti) = (node[0] - 1, node[1] - 1)
	if not a.same(si, ti):
		a.union(si, ti)
		ans += node[2]
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
(V, E) = map(int, input().split())
G = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	G.append((w, s, t))
G.sort()
ans = 0
uf = UnionFind(V)
for i in range(E):
	if not uf.same(G[i][1], G[i][2]):
		ans += G[i][0]
		uf.union(G[i][1], G[i][2])
print(ans)


import array, collections
Edge = collections.namedtuple('Edge', 'start end weight')

class UnionFind(object):

	def __init__(self, number_of_nodes):
		self.par = array.array('L', range(number_of_nodes))
		self.rank = array.array('L', (0 for _ in range(number_of_nodes)))

	def root(self, node):
		if self.par[node] == node:
			return node
		else:
			r = self.root(self.par[node])
			self.par[node] = r
			return r

	def in_the_same_set(self, node1, node2):
		return self.root(node1) == self.root(node2)

	def unite(self, node1, node2):
		x = self.root(node1)
		y = self.root(node2)
		if x == y:
			pass
		elif self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

def compute_mst_kruskal(v_size, edges):
	edges.sort(key=lambda e: e.weight)
	uf = UnionFind(v_size)
	mst = []
	for edge in edges:
		if not uf.in_the_same_set(edge.start, edge.end):
			uf.unite(edge.start, edge.end)
			mst.append(edge)
	return mst
edges = []
(v, e) = map(int, input().split())
for _ in range(e):
	edges.append(Edge(*map(int, input().split())))
print(sum((e.weight for e in compute_mst_kruskal(v, edges))))


def find(x):
	if vertices[x] != x:
		vertices[x] = find(vertices[x])
	return vertices[x]
(nv, ne) = map(int, input().split(' '))
vertices = [i for i in range(nv)]
edges = []
for i in range(ne):
	(s, t, w) = map(int, input().split(' '))
	edges.append((s, t, w))
sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for (s, t, w) in edges:
	u = find(s)
	v = find(t)
	if u != v:
		vertices[u] = v
		sum += w
print(sum)


from heapq import heappop, heappush
(v, e) = map(int, input().split())
G = [[] for _ in range(v)]
for _ in range(e):
	(s, t, w) = map(int, input().split())
	G[s].append((w, t))
	G[t].append((w, s))
been = [0] * v
ans = 0
queue = []
a = (0, 0)
heappush(queue, a)
been[0] = 1
while sum(been) != v:
	while len(queue):
		a = heappop(queue)
		if been[a[1]] == 0:
			been[a[1]] = 1
			break
	ans += a[0]
	for nex in G[a[1]]:
		heappush(queue, (nex[0], nex[1]))
print(ans)


import math, itertools, bisect, sys, copy, queue

def LI():
	return [int(x) for x in sys.stdin.readline().split()]
(V, E) = LI()
q = queue.PriorityQueue()
for _ in range(E):
	(s, t, w) = LI()
	q.put((w, s, t))
g = [i for i in range(V)]
root = [[i] for i in range(V)]
ans = 0
while not q.empty():
	(w, s, t) = q.get()
	if g[s] == g[t]:
		continue
	ans += w
	if len(root[g[s]]) < len(root[g[t]]):
		(s, t) = (t, s)
	g_t = g[t]
	for i in root[g_t]:
		g[i] = g[s]
	root[g[s]].extend(root[g_t])
	root[g_t] = []
print(ans)


from collections import defaultdict
(V, E) = map(int, input().split())
D = 0
tree = []
vertices = defaultdict(set)
for i in range(V):
	tree.append(i)
	vertices[i].add(i)
edges = []
for i in range(E):
	(s, t, d) = map(int, input().split())
	edges.append((s, t, d))
edges.sort(key=lambda x: x[2])
while edges:
	if V == 1:
		break
	(s, t, d) = edges.pop(0)
	if tree[s] != tree[t]:
		new = min(tree[s], tree[t])
		old = max(tree[s], tree[t])
		vertices[new] = vertices[new] | vertices[old]
		for vertex in vertices[old]:
			tree[vertex] = new
		D += d
		V -= 1
print(D)


import sys
readline = sys.stdin.readline
from operator import itemgetter

class UnionFind:

	def __init__(self, n):
		self.p = list(range(n))
		self.rank = [0] * n

	def find_root(self, x):
		if x != self.p[x]:
			self.p[x] = self.find_root(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def unite(self, x, y):
		u = self.find_root(x)
		v = self.find_root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
		else:
			self.p[v] = u
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
(n, m) = map(int, readline().split())
edges = [None] * m
for i in range(m):
	(s, t, w) = map(int, readline().split())
	edges[i] = (s, t, w)
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
	while edges:
		(s, t, w) = edges.pop()
		if not uf.same(s, t):
			uf.unite(s, t)
			break
	ans += w
print(ans)


from collections import defaultdict
from heapq import heappush, heappop
INF = 9999999999999999999999999999

def spanning_tree(G):
	n = len(G)
	T = {}
	added = set([0])
	heap = []
	for v in G[0]:
		heappush(heap, (G[0][v], (0, v)))
	while len(added) < n:
		while True:
			(c, e) = heappop(heap)
			if e[1] not in added:
				break
		T[e] = c
		added.add(e[1])
		for v in G[e[1]]:
			heappush(heap, (G[e[1]][v], (e[1], v)))
	return T
G = {}
(n, m) = [int(v) for v in input().strip().split(' ')]
for i in range(n):
	G[i] = {}
for _ in range(m):
	(s, t, c) = [int(v) for v in input().strip().split(' ')]
	G[s][t] = c
	G[t][s] = c
if m == 0:
	print(0)
	exit()
T = spanning_tree(G)
s = 0
for e in T:
	s += T[e]
print(s)


from typing import List

class UnionFind:

	def __init__(self, V: int) -> None:
		self.V: int = V
		self.pi: List[int] = [i for i in range(V)]
		self.rank: List[int] = [0 for _ in range(V)]

	def findSet(self, x: int) -> int:
		if x != self.pi[x]:
			self.pi[x] = self.findSet(self.pi[x])
		return self.pi[x]

	def same(self, x: int, y: int) -> bool:
		return self.findSet(x) == self.findSet(y)

	def link(self, x: int, y: int) -> None:
		if self.rank[x] > self.rank[y]:
			self.pi[y] = x
		else:
			self.pi[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def unite(self, x: int, y: int) -> None:
		self.link(self.findSet(x), self.findSet(y))

class Edge:

	def __init__(self, source: int, target: int, cost: int) -> None:
		self.source = source
		self.target = target
		self.cost = cost

def kruskal(n: int, edges: List[Edge]) -> int:
	totalCost: int = 0
	edges.sort(key=lambda e: e.cost)
	uf: UnionFind = UnionFind(n + 1)
	for e in edges:
		if not uf.same(e.source, e.target):
			totalCost += e.cost
			uf.unite(e.source, e.target)
	return totalCost
(n, m) = map(int, input().split())
edges: List[Edge] = []
for _ in range(m):
	(s, t, c) = map(int, input().split())
	edges.append(Edge(s, t, c))
ans = kruskal(n, edges)
print(ans)


(v, e) = map(int, input().split())
Edg = []
for _ in range(e):
	(s, t, w) = map(int, input().split())
	Edg.append([w, s, t])
	Edg.append([w, t, s])
Edg.sort(reverse=True)
UF = [i for i in range(v)]
ans = 0
for i in range(2 * e):
	edg = Edg.pop()
	(s, t) = (edg[1], edg[2])
	Ls = [s]
	Lt = [t]
	root_s = UF[s]
	while root_s != s:
		Ls.append(root_s)
		s = root_s
		root_s = UF[root_s]
	root_t = UF[t]
	while root_t != t:
		Lt.append(root_t)
		t = root_t
		root_t = UF[root_t]
	if root_s == root_t:
		continue
	else:
		for j in Lt:
			UF[j] = root_s
		ans += edg[0]
print(ans)


from pprint import pprint
INF = float('inf')
(n_nodes, m_edges) = map(int, input().split())
edges = []
for _ in range(m_edges):
	(u, v, w) = map(int, input().split())
	edges.append([u, v, w])
edges_sorted = sorted(edges, key=lambda e: e[2])

def find_root(v, parents):
	if v == parents[v]:
		return v
	parents[v] = find_root(parents[v], parents)
	return parents[v]

def has_same_root(u, v, parents):
	return find_root(u, parents) == find_root(v, parents)

def unite(u, v, parents):
	root_u = find_root(u, parents)
	root_v = find_root(v, parents)
	parents[root_u] = root_v
	return parents
parents = [i for i in range(n_nodes)]
res = 0
for (u, v, w) in edges_sorted:
	if not has_same_root(u, v, parents):
		res += w
		parents = unite(u, v, parents)
print(res)


from heapq import *

def find(A, x):
	p = A[x]
	if p == x:
		return x
	a = find(A, p)
	A[x] = a
	return a

def union(A, x, y):
	if find(A, x) > find(A, y):
		(bx, by) = (find(A, y), find(A, x))
	else:
		(bx, by) = (find(A, x), find(A, y))
	A[y] = bx
	A[by] = bx
(N, M) = map(int, input().split())
V = [i for i in range(N)]
H = [(0, 0, 0)] * M
for i in range(M):
	(s, t, w) = map(int, input().split())
	H[i] = (w, s, t)
heapify(H)
ans = 0
while H:
	(w, s, t) = heappop(H)
	if find(V, s) != find(V, t):
		union(V, s, t)
		ans += w
print(ans)


import sys
import collections

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def are_same(self, x, y):
		return self.find(x) == self.find(y)
Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
(V, E) = map(int, sys.stdin.readline().split())
edges = sorted([Edge(*map(int, line.split())) for line in sys.stdin], key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
	if not uf.are_same(edge.s, edge.t):
		uf.union(edge.s, edge.t)
		min_cost += edge.cost
print(min_cost)


p = []
rank = []
edge = []
cost = 0

def makeSet(x):
	global p, rank
	p.append(x)
	rank.append(0)

def findSet(x):
	global p
	if x != p[x]:
		p[x] = findSet(p[x])
	return p[x]

def link(x, y):
	global p, rank
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def union(x, y):
	link(findSet(x), findSet(y))

def same(x, y):
	if findSet(x) == findSet(y):
		return 1
	else:
		return 0
[v, e] = list(map(int, input().split()))
for i in range(v):
	makeSet(i)
for i in range(e):
	[s, t, w] = list(map(int, input().split()))
	edge.append([w, s, t])
edge.sort()
while v > 1:
	min = edge.pop(0)
	if not same(min[1], min[2]):
		union(min[1], min[2])
		cost += min[0]
		v -= 1
print(cost)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)
(V, E, *t) = map(int, open(0).read().split())
edges = sorted([(w, s, t) for (s, t, w) in zip(*[iter(t)] * 3)])
uf = UnionFind(V)
ans = 0
for (w, s, t) in edges:
	if not uf.isSame(s, t):
		ans += w
		uf.unite(s, t)
print(ans)


import heapq

def main():
	(nvertices, nedges) = map(int, input().split())
	Adj = [[] for i in range(nvertices)]
	for i in range(nedges):
		(u, v, w) = map(int, input().split())
		Adj[u].append((v, w))
		Adj[v].append((u, w))
	INF = float('inf')
	Q = [(0, 0)]
	for i in range(1, nvertices):
		Q.append((INF, i))
	heapq.heapify(Q)
	key = [INF] * nvertices
	key[0] = 0
	done = [False] * nvertices
	ans = 0
	while Q:
		(val, u) = heapq.heappop(Q)
		if val > key[u]:
			continue
		done[u] = True
		ans += val
		for (v, w) in Adj[u]:
			if not done[v] and w < key[v]:
				key[v] = w
				heapq.heappush(Q, (w, v))
	print(ans)
main()


def root(r):
	if par[r] == r:
		return r
	par[r] = root(par[r])
	return par[r]

def same(x, y):
	return root(x) == root(y)

def unite(x, y):
	x = root(x)
	y = root(y)
	par[x] = y
(v, e) = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key=lambda x: x[2])
par = [i for i in range(v)]
sum = 0
for (i, j, k) in adj:
	if not same(i, j):
		sum += k
		unite(i, j)
print(sum)


import heapq

def prim_heap():
	used = [True] * n
	edgelist = []
	for e in edge[0]:
		heapq.heappush(edgelist, e)
	used[0] = False
	res = 0
	while len(edgelist) != 0:
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, e)
		res += minedge[0]
	return res
(n, w) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(w):
	(x, y, z) = map(int, input().split())
	edge[x].append([z, y])
	edge[y].append([z, x])
print(prim_heap())


class UnionFind:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.height = [0 for i in range(n)]

	def get_root(self, i):
		if self.parent[i] == i:
			return i
		else:
			self.parent[i] = self.get_root(self.parent[i])
			return self.parent[i]

	def unite(self, i, j):
		root_i = self.get_root(i)
		root_j = self.get_root(j)
		if root_i != root_j:
			if self.height[root_i] < self.height[root_j]:
				self.parent[root_i] = root_j
			else:
				self.parent[root_j] = root_i
				if self.height[root_i] == self.height[root_j]:
					self.height[root_i] += 1

	def is_in_group(self, i, j):
		if self.get_root(i) == self.get_root(j):
			return True
		else:
			return False

def kruskal(V, e_list):
	e_cost_sorted = []
	for e in e_list:
		e_cost_sorted.append([e[2], e[0], e[1]])
	e_cost_sorted.sort()
	uf_tree = UnionFind(V)
	cost = 0
	for k in range(len(e_cost_sorted)):
		c = e_cost_sorted[k][0]
		i = e_cost_sorted[k][1]
		j = e_cost_sorted[k][2]
		if not uf_tree.is_in_group(i, j):
			uf_tree.unite(i, j)
			cost += c
	print(cost)
(V, E) = map(int, input().split())
e_list = []
for i in range(E):
	e_list.append(list(map(int, input().split())))
kruskal(V, e_list)


(v, e) = map(int, input().split())
if e == 0:
	print(0)
	exit()

class UnionFind:
	__slots__ = ['_size', '_first_idx', '_parents']

	def __init__(self, size: int, first_index: int=0) -> None:
		self._size = size
		self._first_idx = first_index
		self._parents = [-1] * (size + first_index)

	def find(self, x: int) -> int:
		if self._parents[x] < 0:
			return x
		self._parents[x] = self.find(self._parents[x])
		return self._parents[x]

	def same(self, x: int, y: int) -> bool:
		return self.find(x) == self.find(y)

	def unite(self, x: int, y: int) -> bool:
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return False
		if self._parents[x] > self._parents[y]:
			(x, y) = (y, x)
		self._parents[x] += self._parents[y]
		self._parents[y] = x
		return True

	def size(self, x: int) -> int:
		return -self._parents[self.find(x)]

	def group_count(self) -> int:
		return sum((1 for i in self._parents if i < 0)) - self._first_idx

	def connected(self) -> bool:
		return self._parents[self.find(self._first_idx)] == -self._size
edges = sorted([list(map(int, input().split())) for i in range(e)], key=lambda x: x[-1])
uf = UnionFind(v)
(n, m, su) = edges[0]
uf.unite(n, m)
for (a, s, d) in edges:
	if uf.same(a, s):
		continue
	uf.unite(a, s)
	su += d
	if uf.size(n) == v:
		print(su)
		exit()


from collections import defaultdict
import heapq
(vertices, edges) = (int(n) for n in input().split(' '))
conn = defaultdict(set)
weight = defaultdict(dict)
for i in range(edges):
	(v1, v2, w) = (int(n) for n in input().split(' '))
	conn[v1] |= {v2}
	conn[v2] |= {v1}
	weight[v1][v2] = w
	weight[v2][v1] = w
queue = []
heapq.heapify(queue)
heapq.heappush(queue, [0, 0])
went = set()
went_vertices = 0
answer_weight = 0
while went_vertices < vertices:
	(here_weight, here_v) = heapq.heappop(queue)
	if here_v in went:
		continue
	went |= {here_v}
	for c in conn[here_v]:
		if c not in went:
			heapq.heappush(queue, [weight[here_v][c], c])
	answer_weight += here_weight
	went_vertices += 1
print(answer_weight)


import heapq
(V, E) = map(int, input().split())
C = [[] for _ in range(V)]
for _ in range(E):
	(s, t, w) = map(int, input().split())
	C[s].append([t, w])
	C[t].append([s, w])
visited = [False] * V
visited[0] = True
q = []
node = 0
node_cnt = 1
ans = 0
while node_cnt < V:
	for (adj, w) in C[node]:
		if not visited[adj]:
			heapq.heappush(q, (w, adj))
	while 1:
		(weight, node) = heapq.heappop(q)
		if not visited[node]:
			break
	visited[node] = True
	ans += weight
	node_cnt += 1
print(ans)


import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple

class DisjointSet(object):

	def __init__(self, size):
		self.rank = []
		self.p = []
		for i in range(size):
			self.makeSet(i)

	def makeSet(self, x):
		self.p.insert(x, x)
		self.rank.insert(x, 0)

	def same(self, x, y):
		return self.findSet(x) == self.findSet(y)

	def unite(self, x, y):
		self.link(self.findSet(x), self.findSet(y))

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def findSet(self, x):
		if x != self.p[x]:
			self.p[x] = self.findSet(self.p[x])
		return self.p[x]

def kruskal(V, E, es):
	es.sort(key=lambda x: x.c)
	uf = DisjointSet(V)
	res = 0
	for i in range(E):
		e = es[i]
		if not uf.same(e.u, e.v):
			uf.unite(e.u, e.v)
			res += e.c
	return res
edge = namedtuple('edge', ['u', 'v', 'c'])

def main(args):
	(V, E) = map(int, input().split())
	es = []
	for _ in range(E):
		(s, t, w) = map(int, input().split())
		es.append(edge(s, t, w))
	result = kruskal(V, E, es)
	print(result)
main(sys.argv[1:])


import sys
readline = sys.stdin.readline
from operator import itemgetter

class UnionFind:

	def __init__(self, n):
		self.p = list(range(n))
		self.rank = [0] * n

	def find_root(self, x):
		if x != self.p[x]:
			self.p[x] = self.find_root(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def unite(self, x, y):
		u = self.find_root(x)
		v = self.find_root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
		else:
			self.p[v] = u
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
(n, m) = map(int, readline().split())
edges = [tuple(map(int, readline().split())) for _ in [0] * m]
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
	while edges:
		(s, t, w) = edges.pop()
		if not uf.same(s, t):
			uf.unite(s, t)
			break
	ans += w
print(ans)


import array
import collections
import heapq
AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
INF = 2 ** 31 - 1
NO_VERTEX = -1

def compute_mst_prim(max_v, adj_list):
	pred = collections.defaultdict(lambda : NO_VERTEX)
	key = collections.defaultdict(lambda : INF)
	key[0] = 0
	pq = [(key[v], v) for v in range(max_v)]
	heapq.heapify(pq)
	in_pq = array.array('B', (True for _ in range(max_v)))
	while pq:
		(_, u) = heapq.heappop(pq)
		in_pq[u] = False
		for (v, v_cost) in adj_list[u]:
			if in_pq[v]:
				weight = v_cost
				if weight < key[v]:
					pred[v] = u
					key[v] = weight
					heapq.heappush(pq, (weight, v))
					in_pq[v] = True
	return (pred, key)

def main():
	(max_v, max_e) = map(int, input().split())
	adjacency_list = collections.defaultdict(set)
	for _ in range(max_e):
		(s, t, w) = map(int, input().split())
		adjacency_list[s].add(AdjacentVertex(t, w))
		adjacency_list[t].add(AdjacentVertex(s, w))
	(_, key) = compute_mst_prim(max_v, adjacency_list)
	print(sum(key.values()))
main()


V = 0
E = 0
edge = []
p = []
rank = []
answer = 0
count = 0

def makeset(x):
	p[x] = x
	rank[x] = 0

def union(x, y):
	link(findset(x), findset(y))

def link(x, y):
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
		if rank[x] == rank[y]:
			rank[y] = rank[y] + 1

def findset(x):
	if x != p[x]:
		p[x] = findset(p[x])
	return p[x]

def takeThird(elem):
	return elem[2]
(v, e) = map(int, input().split())
V = v
E = e
while True:
	try:
		(s, t, w) = map(int, input().split())
	except:
		break
	else:
		edge.append([s, t, w])
edge.sort(key=takeThird)
for i in range(V):
	p.append(None)
	rank.append(None)
for i in range(V):
	makeset(i)
for i in range(len(edge)):
	if count == V - 1:
		break
	if findset(edge[i][0]) == findset(edge[i][1]):
		continue
	union(edge[i][0], edge[i][1])
	answer += edge[i][2]
	count += 1
print(answer)


ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))
(v, e) = mi()
path = []
for i in range(e):
	a = li()
	path.append([a[2], a[0], a[1]])
path.sort()

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.d = [-1] * n

	def find(self, x):
		if self.d[x] < 0:
			return x
		self.d[x] = self.find(self.d[x])
		return self.d[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		if self.d[x] > self.d[y]:
			(x, y) = (y, x)
		self.d[x] += self.d[y]
		self.d[y] = x
		return True

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.d[self.find(x)]
uf = UnionFind(v)
ans = 0
for i in path:
	w = i[0]
	s = i[1]
	t = i[2]
	if uf.same(s, t):
		pass
	else:
		uf.union(s, t)
		ans += w
print(ans)


from heapq import heappush, heappop

class Prim:

	def __init__(self, V, E, start=0, INF=10 ** 9):
		self.prim(V, E, start, INF)

	def prim(self, V, E, start=0, INF=10 ** 9):
		used = [False] * V
		self.mincost = 0
		que = []
		heappush(que, (0, 0))
		while len(que) > 0:
			(cost, v) = heappop(que)
			if used[v]:
				continue
			used[v] = True
			self.mincost += cost
			for (to, c) in E[v]:
				heappush(que, (c, to))

	def minCost(self):
		return self.mincost
(V, E) = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edge[s].append((t, w))
	edge[t].append((s, w))
msp = Prim(V, edge)
print(msp.minCost())


class UnionFindTree:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [1] * (n + 1)

	def find_root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find_root(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find_root(x)
		y = self.find_root(y)
		if x == y:
			return
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def is_same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def count_node(self, x):
		return -1 * self.root[self.find_root(x)]
(v, e) = map(int, input().split())
edges = []
for _ in range(e):
	(s, t, w) = map(int, input().split())
	edges.append((w, s, t))
edges.sort()

def kuruskal(n, edges):
	uft = UnionFindTree(n)
	res = 0
	for e in edges:
		(w, s, t) = e
		if not uft.is_same(s, t):
			res += w
			uft.unite(s, t)
	return res
print(kuruskal(v, edges))


from operator import itemgetter
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
input = stdin.readline

class Union_find:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find_root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find_root(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		(x, y) = (self.find_root(x), self.find_root(y))
		if x == y:
			return
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def count(self, x):
		return -self.root[self.find_root(x)]
(v, e) = map(int, input().split())
graph = Union_find(v)
a = sorted([list(map(int, input().split())) for _ in range(e)], key=itemgetter(2))
ans = 0
for i in a:
	(s, t, w) = i
	if not graph.same(s, t):
		graph.unite(s, t)
		ans += w
print(ans)


(v, e) = map(int, input().split())
import heapq
h = []
for i in range(e):
	(s, t, w) = map(int, input().split())
	heapq.heappush(h, (w, s, t))
p = [i for i in range(v)]
rank = [0 for i in range(v)]

def union(x, y):
	link(findSet(x), findSet(y))

def link(x, y):
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
		if rank[x] == rank[y]:
			rank[y] = rank[y] + 1

def findSet(x):
	if x != p[x]:
		p[x] = findSet(p[x])
	return p[x]

def unite(x, y):
	union(x, y)

def same(x, y):
	x = findSet(x)
	y = findSet(y)
	if x == y:
		return True
	else:
		return False
s = 0
for i in range(e):
	edge = heapq.heappop(h)
	if same(edge[1], edge[2]) == False:
		s = s + edge[0]
		unite(edge[1], edge[2])
print(s)


from heapq import heappush, heappop
line = input()
(v, e) = list(map(int, line.split()))
edge = {}
edge[0] = [[0, 0]]
for _ in range(0, e):
	line = input()
	(s, t, w) = list(map(int, line.split()))
	if s not in edge:
		edge[s] = [[t, w]]
	else:
		edge[s] += [[t, w]]
	if t not in edge:
		edge[t] = [[s, w]]
	else:
		edge[t] += [[s, w]]

def solve(v, edge):
	q = []
	vtx = set([i for i in range(0, v)])
	for (t, w) in edge[0]:
		heappush(q, (w, 0, t))
	vn = set([0])
	en = []
	cost = 0
	while len(vn) < v:
		w = s = t = 0
		qq = []
		while q:
			(w, s, t) = heappop(q)
			if s in vn and t not in vn:
				(s, t) = (t, s)
				break
			if s not in vn and t in vn:
				break
		vn.add(s)
		en += [(s, t)]
		cost += w
		for (t, w) in edge[s]:
			heappush(q, (w, s, t))
	return cost
print(solve(v, edge))


import sys

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.p = [i for i in range(n + 5)]
		self.rank = [0 for i in range(n + 5)]

	def find_set(self, x):
		if self.p[x] != x:
			self.p[x] = self.find_set(self.p[x])
		return self.p[x]

	def unite(self, x, y):
		(px, py) = (self.find_set(x), self.find_set(y))
		if px == py:
			return
		if self.rank[px] > self.rank[py]:
			self.p[py] = px
		else:
			self.p[px] = py
			if self.rank[px] == self.rank[py]:
				self.rank[py] += 1

def main():
	sys.setrecursionlimit(int(100000.0))
	(nvertices, nedges) = map(int, input().split())
	E = []
	uf = UnionFind(nvertices)
	for i in range(nedges):
		(s, t, w) = map(int, input().split())
		E.append((w, s, t))
	E.sort()
	ans = 0
	for (w, s, t) in E:
		if uf.find_set(s) != uf.find_set(t):
			ans += w
			uf.unite(s, t)
	print(ans)
main()


from sys import stdin

def read_edge(e):
	E = []
	for _ in range(e):
		line = stdin.readline().strip().split()
		u = line[0]
		v = line[1]
		w = line[2]
		E.append((int(w), int(u), int(v)))
	return E

class DisjointSet(object):

	def __init__(self, n):
		self.parent = [None] * (n + 1)
		self.rank = [None] * (n + 1)

	def make_set(self, x):
		if self.parent[x] == None:
			self.parent[x] = x
			self.rank[x] = 0

	def find_set(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find_set(self.parent[x])
		return self.parent[x]

	def unite(self, x, y):
		self.link(self.find_set(x), self.find_set(y))

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.parent[y] = x
		else:
			self.parent[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def same(self, x, y):
		return self.find_set(x) == self.find_set(y)

def kuruskal(n, E):
	S = DisjointSet(n)
	for i in range(n):
		S.make_set(i)
	K = []
	for i in sorted(E):
		if S.find_set(i[1]) != S.find_set(i[2]):
			S.unite(i[1], i[2])
			K.append(i[0])
	return K
(n, e) = [int(i) for i in input().split()]
E = read_edge(e)
K = kuruskal(n, E)
print(sum(K))


import heapq
(v, e) = map(int, input().split())
edges = []
for i in range(e):
	(s, t, w) = map(int, input().split())
	heapq.heappush(edges, (w, (s, t)))

class Node:

	def __init__(self, id):
		self.id = id
		self.p = self
		self.rank = 0

class DisjointSet:

	def __init__(self, n):
		self.nodes = {}
		for i in range(n):
			self.makeSet(i)

	def makeSet(self, i):
		self.nodes[i] = Node(i)

	def findSet(self, x):
		if x.p is not x:
			x.p = self.findSet(x.p)
		return x.p

	def unite(self, x, y):
		px = self.findSet(x)
		py = self.findSet(y)
		if px.rank > py.rank:
			py.p = px
		else:
			px.p = py
		if x.rank == y.rank:
			py.rank += 1

	def bool(self, x, y):
		return self.findSet(x) == self.findSet(y)

def kruskal(v, edges):
	S = DisjointSet(v)
	K = []
	while len(edges):
		(w, edge) = heapq.heappop(edges)
		(x, y) = (S.nodes[edge[0]], S.nodes[edge[1]])
		if not S.bool(x, y):
			S.unite(x, y)
			K.append((edge, w))
	return K
K = kruskal(v, edges)
print(sum(map(lambda x: x[1], K)))


import sys, collections
sys.setrecursionlimit(10000)
INF = float('inf')
(V, E) = map(int, sys.stdin.readline().split())
stw = tuple((tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(E)))
wst = [[w, s, t] for (s, t, w) in stw]
wst.sort()
parents = list(range(V))

def find(x):
	while parents[x] != x:
		x = parents[x]
		parents[x] = parents[parents[x]]
	return x

def union(s, t):
	sp = find(s)
	tp = find(t)
	if sp == tp:
		pass
	elif sp < tp:
		parents[sp] = tp
	else:
		parents[tp] = sp
INF = float('inf')
ret = 0
for (w, s, t) in wst:
	if find(s) != find(t):
		union(s, t)
		ret += w
print(ret)


class UnionFind:

	def __init__(self, n):
		self.parent = [None] * n
		self.rank = [None] * n
		self._size = [1] * n
		for i in range(n):
			self.parent[i] = i
			self.rank[i] = 0

	def root_of(self, x):
		children = [x]
		while self.parent[x] != x:
			x = self.parent[x]
			children.append(x)
		for ch in children:
			self.parent[ch] = x
		return x

	def union(self, x, y):
		rx = self.root_of(x)
		ry = self.root_of(y)
		if rx == ry:
			return
		if self.rank[rx] < self.rank[ry]:
			self.parent[rx] = ry
			self._size[ry] += self._size[rx]
		else:
			self.parent[ry] = rx
			self._size[rx] += self._size[ry]
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] += 1

	def same(self, x, y):
		return self.root_of(x) == self.root_of(y)

def kruskal(E, n):
	E.sort()
	cost = 0
	uf = UnionFind(n)
	for (c, (x, y)) in E:
		if not uf.same(x, y):
			cost += c
			uf.union(x, y)
	return cost
(n, m) = [int(x) for x in input().split()]
E = []
for _ in range(m):
	(s, t, w) = [int(x) for x in input().split()]
	E.append((w, (s, t)))
print(kruskal(E, n))


from heapq import heappop, heappush, heapify

class Graph:

	def __init__(self, n, edge, directed=False):
		self.n = n
		self.graph = [[] for _ in range(n)]
		for e in edge:
			self.graph[e[0]].append((e[1], e[2]))
			if not directed:
				self.graph[e[1]].append((e[0], e[2]))

	def prim(self):
		used = [False for _ in range(self.n)]
		used[0] = True
		heap = [(cost, adj) for (adj, cost) in self.graph[0]]
		heapify(heap)
		res = 0
		while heap:
			(cost, node) = heappop(heap)
			if used[node]:
				continue
			used[node] = True
			res += cost
			for (adj, adjcost) in self.graph[node]:
				if used[adj]:
					continue
				heappush(heap, (adjcost, adj))
		return res
import sys
input = sys.stdin.readline
(V, E) = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(E)]
g = Graph(V, edge)
print(g.prim())


import heapq
(V, E) = map(int, input().split())
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
	(s, t, w) = map(int, input().split())
	nodes[s].append(t)
	cost[s].append(w)
	nodes[t].append(s)
	cost[t].append(w)
visited = [False] * V
total = 0
h = [(0, -1, 0)]
while h:
	(c, s, t) = heapq.heappop(h)
	if visited[t]:
		continue
	total += c
	visited[t] = True
	for i in range(len(nodes[t])):
		nv = nodes[t][i]
		if not visited[nv]:
			heapq.heappush(h, (cost[t][i], t, nv))
print(total)


class UnionFind:
	MAX_N = 0
	PAR = []
	RANK = []

	def __init__(self, n):
		self.MAX_N = n
		self.PAR = [i for i in range(n)]
		self.RANK = [0] * n

	def find(self, x):
		if self.PAR[x] == x:
			return x
		else:
			self.PAR[x] = self.find(self.PAR[x])
			return self.PAR[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.RANK[x] < self.RANK[y]:
			self.PAR[x] = y
		else:
			self.PAR[y] = x
			if self.RANK[x] == self.RANK[y]:
				self.RANK[x] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)

def kruskal(Edge):
	Edge.sort(key=lambda x: x[2])
	data = UnionFind(V)
	res = 0
	for i in range(E):
		u = Edge[i][0]
		v = Edge[i][1]
		d = Edge[i][2]
		if data.same(u, v) == False:
			data.unite(u, v)
			res += d
	return res
(V, E) = map(int, input().split())
Edge = []
for _ in range(E):
	Edge.append(list(map(int, input().split())))
ans = kruskal(Edge)
print(ans)


import heapq
from collections import defaultdict
INF = float('inf')
(V, E) = map(int, input().split())
Adj_list = defaultdict(set)
for i in range(E):
	(s, t, w) = map(int, input().split())
	Adj_list[s].add((t, w))
	Adj_list[t].add((s, w))

def prim(x):
	d = [INF] * x
	d[0] = 0
	isVisited = [False] * x
	hq = [(0, 0)]
	while hq:
		u = heapq.heappop(hq)[1]
		isVisited[u] = True
		for (v, c) in Adj_list[u]:
			if not isVisited[v] and d[v] > c:
				d[v] = c
				heapq.heappush(hq, (c, v))
	return sum(d)
print(prim(V))


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [i for i in range(n + 1)]
		self.size = [1] * (n + 1)

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def unite(self, x, y):
		xRoot = self.find(x)
		yRoot = self.find(y)
		if xRoot == yRoot:
			return
		if self.size[xRoot] > self.size[yRoot]:
			self.parents[yRoot] = xRoot
			self.size[xRoot] += self.size[yRoot]
			self.size[yRoot] = 0
		else:
			self.parents[xRoot] = yRoot
			self.size[yRoot] += self.size[xRoot]
			self.size[xRoot] = 0
(V, E) = map(int, input().split())
tree = UnionFind(V)
edges = [list(map(int, input().split())) for _ in range(E)]
edges.sort(key=lambda x: x[2])
cost = 0
for (s, t, w) in edges:
	if tree.find(s) != tree.find(t):
		cost += w
		tree.unite(s, t)
print(cost)


(V, E) = map(int, input().split())
VWT = [list(map(int, input().split())) for i in range(E)]

class UF:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * n
		self.rank = [0] * n

	def __del__(self):
		pass

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.root[y] += self.root[x]
			self.root[x] = y
		else:
			self.root[x] += self.root[y]
			self.root[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def count(self, x):
		return -self.root[self.find(x)]
uf = UF(V)
VWT = sorted(VWT, key=lambda x: x[2])
ans = 0
for vwt in VWT:
	(v, w, t) = vwt
	if not uf.same(v, w):
		uf.unite(v, w)
		ans += t
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def root(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.root(self.parents[x])
			return self.parents[x]

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.root(x) == self.root(y)

def main():
	(V, E) = map(int, input().split())
	edge_q = sorted([tuple(map(int, input().split())) for _ in range(E)], key=lambda x: x[2])
	ans = 0
	forest = UnionFind(V)
	for (s, t, w) in edge_q:
		if forest.same(s, t):
			continue
		forest.unite(s, t)
		ans += w
	print(ans)
main()


import heapq
(V, E) = map(int, input().split())
es = [[] for _ in range(V)]
q = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	heapq.heappush(q, (w, s, t))

class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.rank = [0] * N
		self.count = 0

	def root(self, a):
		if self.parent[a] == a:
			return a
		else:
			self.parent[a] = self.root(self.parent[a])
			return self.parent[a]

	def is_same(self, a, b):
		return self.root(a) == self.root(b)

	def unite(self, a, b):
		ra = self.root(a)
		rb = self.root(b)
		if ra == rb:
			return
		if self.rank[ra] < self.rank[rb]:
			self.parent[ra] = rb
		else:
			self.parent[rb] = ra
			if self.rank[ra] == self.rank[rb]:
				self.rank[ra] += 1
		self.count += 1
uf = UnionFind(V)
total = 0
while q:
	(w, s, t) = heapq.heappop(q)
	if not uf.is_same(s, t):
		uf.unite(s, t)
		total += w
print(total)


from heapq import heappush, heappop
INF = 10 ** 20
(v_num, e_num) = map(int, input().split())
edges_lst = [[] for _ in range(v_num)]
dist_lst = [INF for _ in range(v_num)]
min_dis = INF
for _ in range(e_num):
	(s, t, dist) = map(int, input().split())
	edges_lst[s].append((dist, t))
	edges_lst[t].append((dist, s))
	if min_dis > dist:
		min_dis = dist
		(node1, node2) = (s, t)
if v_num == 1:
	print(0)
else:
	que = []
	for v in edges_lst[node1]:
		heappush(que, v)
	for v in edges_lst[node2]:
		heappush(que, v)
		S = {node1, node2}
		ans = min_dis
	while len(S) != v_num:
		(dist, node) = heappop(que)
		if node not in S:
			S.add(node)
			ans += dist
			for (dist2, v) in edges_lst[node]:
				if v not in S:
					heappush(que, (dist2, v))
	print(ans)


from collections import defaultdict

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = []

	def addEdge(self, s, t, w):
		self.graph.append([s, t, w])

	def find(self, parent, i):
		if parent[i] == i:
			return i
		return self.find(parent, parent[i])

	def union(self, parent, rank, x, y):
		xroot = self.find(parent, x)
		yroot = self.find(parent, y)
		if rank[xroot] < rank[yroot]:
			parent[xroot] = yroot
		elif rank[xroot] > rank[yroot]:
			parent[yroot] = xroot
		else:
			parent[yroot] = xroot
			rank[xroot] += 1

	def KruskalMST(self):
		sum = 0
		result = []
		i = 0
		e = 0
		self.graph = sorted(self.graph, key=lambda item: item[2])
		parent = []
		rank = []
		for node in range(self.V):
			parent.append(node)
			rank.append(0)
		while e < self.V - 1:
			(s, t, w) = self.graph[i]
			i += 1
			x = self.find(parent, s)
			y = self.find(parent, t)
			if x != y:
				e = e + 1
				result.append([s, t, w])
				self.union(parent, rank, x, y)
		for (s, t, weight) in result:
			sum += weight
		print(sum)
(V, E) = (int(z) for z in input().split())
g = Graph(V)
for i in range(E):
	(s, t, w) = (int(z) for z in input().split())
	g.addEdge(s, t, w)
g.KruskalMST()


import sys
readline = sys.stdin.readline
from operator import itemgetter

class UnionFind:

	def __init__(self, n):
		self.p = list(range(n))
		self.rank = [0] * n

	def find_root(self, x):
		if x != self.p[x]:
			self.p[x] = self.find_root(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def unite(self, x, y):
		u = self.find_root(x)
		v = self.find_root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
		else:
			self.p[v] = u
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
(n, m) = map(int, readline().split())
edges = []
for _ in [0] * m:
	(s, t, w) = map(int, readline().split())
	edges.append((s, t, w))
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
	while edges:
		(s, t, w) = edges.pop()
		if not uf.same(s, t):
			uf.unite(s, t)
			break
	ans += w
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
(v, e) = map(int, input().split())
road = []
for i in range(e):
	(a, b, c) = list(map(int, input().split()))
	road.append((a, b, c))
road.sort(key=lambda x: x[2])
uf = UnionFind(v)
cost = 0
cnt = 0
for i in range(e):
	a = road[i][0]
	b = road[i][1]
	c = road[i][2]
	if uf.same(a, b) == False:
		uf.union(a, b)
		cost += c
		cnt += 1
		if cnt == v - 1:
			break
print(cost)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [i for i in range(n)]
		self.rank = [0 for i in range(n)]
		self.siz = [1 for i in range(n)]

	def find(self, x):
		if self.par[x] == x:
			return x
		return self.find(self.par[x])

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] > self.rank[y]:
			self.par[y] = x
			self.siz[x] += self.siz[y]
		else:
			self.par[x] = y
			self.siz[y] += self.siz[x]
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return self.siz[self.find(x)]

def kruskal(n, m):
	res = 0
	uf = UnionFind(n)
	for i in range(m):
		(w, s, t) = es[i]
		if uf.same(s, t):
			continue
		uf.unite(s, t)
		res += w
	return res
(V, E) = map(int, input().split())
es = []
for i in range(E):
	(s, t, w) = map(int, input().split())
	es.append([w, s, t])
es.sort(key=lambda x: x[0])
res = kruskal(V, E)
print(res)


(num_v, num_e) = input().split()
edges = []
verticies = []
for i in range(int(num_e)):
	(v, u, w) = input().split()
	e = (v, u, int(w))
	edges.append(e)
for v in range(int(num_v)):
	v = str(v)
	verticies.append(v)
graph = {'verticies': verticies, 'edges': edges}
parent = {}
g_len = {}

def group(v):
	parent[v] = v
	g_len[v] = 0

def my_parent(v):
	if parent[v] != v:
		parent[v] = my_parent(parent[v])
	return parent[v]

def union(v, u):
	g_v = my_parent(v)
	g_u = my_parent(u)
	if g_v != g_u:
		if g_len[g_v] >= g_len[g_u]:
			parent[g_u] = parent[g_v]
			g_len[g_v] += 1
		else:
			parent[g_v] = parent[g_u]
			g_len[g_u] += 1

def kruskal(graph):
	g_list = []
	sum_w = 0
	for v in graph['verticies']:
		group(v)
	edges = graph['edges']
	edges.sort(key=lambda edges: edges[2])
	for edge in edges:
		(v, u, weight) = edge
		if my_parent(v) != my_parent(u):
			union(v, u)
			g_list.append(edge)
			sum_w = sum_w + weight
	return sum_w
print(kruskal(graph))


class UnionFind(object):

	def __init__(self, n):
		self.par = [-1] * n

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		else:
			if self.par[x] > self.par[y]:
				(x, y) = (y, x)
			self.par[x] += self.par[y]
			self.par[y] = x
			return True

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.par[self.find(x)]
from heapq import heappush, heappop
edges = []
(N, M) = map(int, input().split())
for _ in range(M):
	(si, ti, wi) = map(int, input().split())
	heappush(edges, (wi, si, ti))
uf = UnionFind(N)
cost = 0
mst = []
while len(edges) > 0:
	(w, u, v) = heappop(edges)
	if not uf.same(u, v):
		uf.unite(u, v)
		mst.append((u, v))
		cost += w
print(cost)


import heapq

def prim_heap():
	used = [True] * n
	edgelist = []
	for e in edge[0]:
		heapq.heappush(edgelist, e)
	used[0] = False
	res = 0
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, e)
		res += minedge[0]
	return res
(n, w) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(w):
	(x, y, z) = map(int, input().split())
	edge[x].append([z, y])
	edge[y].append([z, x])
print(prim_heap())


import sys
import heapq as hp
(WHITE, GRAY, BLACK) = (0, 1, 2)

def generate_adj_table(v_table):
	for each in v_table:
		(v_from, v_to, edge_weight) = map(int, each)
		init_adj_table[v_from][v_to] = edge_weight
		init_adj_table[v_to][v_from] = edge_weight
	return init_adj_table

def prim_span_tree():
	distance[init_v] = 0
	parent[init_v] = -1
	distance_heap = []
	hp.heappush(distance_heap, (0, init_v))
	while distance_heap:
		current_vertex = hp.heappop(distance_heap)[1]
		color[current_vertex] = BLACK
		for (adj_vertex, adj_weight) in adj_table[current_vertex].items():
			if color[adj_vertex] is not BLACK:
				if adj_weight < distance[adj_vertex]:
					distance[adj_vertex] = adj_weight
					parent[adj_vertex] = current_vertex
					color[adj_vertex] = GRAY
					hp.heappush(distance_heap, (adj_weight, adj_vertex))
	return distance
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
parent = [-1] * vertices
distance = [float('inf')] * vertices
color = [WHITE] * vertices
init_v = 0
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
print(sum(prim_span_tree()))


import sys
import heapq

def link(x, y):
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def find_set(x):
	if x != p[x]:
		p[x] = find_set(p[x])
	return p[x]

def unite(x, y):
	link(find_set(x), find_set(y))

def same(x, y):
	x = find_set(x)
	y = find_set(y)
	if x == y:
		return True
	else:
		return False
h = []
line = sys.stdin.readline()
(v, e) = map(int, line.split())
p = [i for i in range(v)]
rank = [0 for _ in range(v)]
for i in range(e):
	line = sys.stdin.readline()
	(s, t, w) = map(int, line.split())
	heapq.heappush(h, (w, s, t))
s = 0
for i in range(e):
	elm = heapq.heappop(h)
	if not same(elm[1], elm[2]):
		s = s + elm[0]
		unite(elm[1], elm[2])
print(s)


def find(x):
	if parents[x] != x:
		parents[x] = find(parents[x])
	return parents[x]
(nv, ne) = map(int, input().split(' '))
parents = [i for i in range(nv)]
edges = []
for i in range(ne):
	(s, t, w) = map(int, input().split(' '))
	edges.append((s, t, w))
sum = 0
edges.sort(key=lambda tup: tup[2])
for (s, t, w) in edges:
	u = find(s)
	v = find(t)
	if u != v:
		parents[u] = v
		sum += w
print(sum)


class DisjointSet:

	def __init__(self, size):
		self.rank = [0] * size
		self.p = list(range(size))

	def findSet(self, x):
		if x != self.p[x]:
			self.p[x] = self.findSet(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.findSet(x) == self.findSet(y)

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def unite(self, x, y):
		self.link(self.findSet(x), self.findSet(y))

class Edge:

	def __init__(self, source=0, target=0, cost=0):
		self.source = source
		self.target = target
		self.cost = cost

def kruskal(n, edges):
	totalCost = 0
	edges.sort(key=lambda e: e.cost)
	dset = DisjointSet(n)
	for e in edges:
		if not dset.same(e.source, e.target):
			totalCost += e.cost
			dset.unite(e.source, e.target)
	return totalCost
(n, m) = [int(v) for v in input().split()]
edges = []
for i in range(m):
	(s, t, w) = [int(v) for v in input().split()]
	edges.append(Edge(s, t, w))
print(kruskal(n, edges))


from heapq import *

def prim_heap():
	used = [False] * n
	e_lst = []
	for e in edge[0]:
		heappush(e_lst, e)
	used[0] = True
	res = 0
	while e_lst:
		e_min = heappop(e_lst)
		v = e_min[1]
		if used[v]:
			continue
		used[v] = True
		for e in edge[v]:
			if not used[e[1]]:
				heappush(e_lst, e)
		res += e_min[0]
	return res
(n, k) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(k):
	(s, t, w) = map(int, input().split())
	edge[s].append((w, t))
	edge[t].append((w, s))
print(prim_heap())


from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
G = []
for _ in [0] * M:
	(a, b, c) = map(int, input().split())
	heappush(G, (c, a, b))

class UnionFind:

	def __init__(self, n=0):
		self.d = [-1] * n
		self.u = n

	def root(self, x):
		if self.d[x] < 0:
			return x
		self.d[x] = self.root(self.d[x])
		return self.d[x]

	def unite(self, x, y):
		(x, y) = (self.root(x), self.root(y))
		if x == y:
			return False
		if x > y:
			(x, y) = (y, x)
		self.d[x] += self.d[y]
		self.d[y] = x
		self.u -= 1
		return True

	def same(self, x, y):
		return self.root(x) == self.root(y)

	def size(self, x):
		return -self.d[self.root(x)]

	def num_union(self):
		return self.u
u = UnionFind(N)
ans = 0
while u.num_union() > 1:
	(c, a, b) = heappop(G)
	if u.same(a, b):
		continue
	u.unite(a, b)
	ans += c
print(ans)


import heapq

def makeSet(x):
	p[x] = x
	rank[x] = 0

def union(x, y):
	link(findSet(x), findSet(y))

def link(x, y):
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def findSet(x):
	if x != p[x]:
		p[x] = findSet(p[x])
	return p[x]
(v, e) = map(int, input().split())
edge = [[] for _ in range(v)]
p = [0] * v
rank = [0] * v
for x in range(v):
	makeSet(x)
S = []
ans = 0
for _ in range(e):
	(s, t, w) = map(int, input().split())
	heapq.heappush(S, [w, s, t])
while S:
	(w, s, t) = heapq.heappop(S)
	if findSet(s) != findSet(t):
		union(s, t)
		ans += w
print(ans)


import sys
readline = sys.stdin.readline

class UnionFind:
	__slots__ = ['nodes']

	def __init__(self, n: int) -> None:
		self.nodes = [-1] * n

	def get_root(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.get_root(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y) = (self.get_root(x), self.get_root(y))
		if root_x != root_y:
			(bigroot, smallroot) = (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
			self.nodes[bigroot] += self.nodes[smallroot]
			self.nodes[smallroot] = bigroot
			return True
		else:
			return False

def kruskal(n: int, edges: list) -> int:
	edges.sort()
	tree = UnionFind(n)
	total = 0
	cnt = 0
	for (w, s, t) in edges:
		if tree.unite(s, t):
			cnt += 1
			total += w
			if cnt == n - 1:
				break
	return total
(V, E) = map(int, readline().split())
edges = []
append = edges.append
for _ in [None] * E:
	(s, t, w) = map(int, readline().split())
	append((w, s, t))
print(kruskal(V, edges))


(v, e) = map(int, input().split())
p = [i for i in range(v)]
E = [list(map(int, input().split())) for _ in range(e)]
E = sorted(E, key=lambda x: x[2])

def root(x):
	if p[x] == x:
		return x
	p[x] = root(p[x])
	return p[x]
ans = 0
for edg in E:
	(a, b, w) = edg
	if root(a) != root(b):
		ans += w
		p[root(a)] = root(b)
print(ans)


(v, e) = map(int, input().split())
from heapq import heappush, heappop
edges = []
for _ in range(e):
	(s, t, w) = map(int, input().split())
	heappush(edges, (w, s, t))
par = [-1] * v
rank = [0] * v

def find(x):
	if par[x] < 0:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	rootx = find(x)
	rooty = find(y)
	if rootx == rooty:
		return False
	else:
		if rank[rootx] < rank[rooty]:
			par[rootx] = rooty
		else:
			par[rooty] = rootx
			if rank[rootx] == rank[rooty]:
				rank[rootx] += 1
		return True

def same(x, y):
	return find(x) == find(y)
ans = 0
while edges:
	(w, s, t) = heappop(edges)
	if not same(s, t):
		ans += w
		unite(s, t)
print(ans)


def root(x):
	if par[x] == x:
		return x
	par[x] = root(par[x])
	return par[x]

def same(x, y):
	return root(x) == root(y)

def unite(x, y):
	x = root(x)
	y = root(y)
	par[x] = y
(v, e) = map(int, input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key=lambda x: x[2])
par = [i for i in range(v)]
sum = 0
for (i, j, k) in adj:
	if not same(i, j):
		sum += k
		unite(i, j)
print(sum)


def find(x):
	if parents[x] != x:
		parents[x] = find(parents[x])
	return parents[x]
(nv, ne) = map(int, input().split(' '))
parents = [i for i in range(nv)]
edges = []
for i in range(ne):
	(s, t, w) = map(int, input().split(' '))
	edges.append((s, t, w))
sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for (s, t, w) in edges:
	u = find(s)
	v = find(t)
	if u != v:
		parents[u] = v
		sum += w
print(sum)


import sys
file_input = sys.stdin
(v_num, e_num) = map(int, file_input.readline().split())
E = []
for line in file_input:
	(s, t, w) = map(int, line.split())
	E.append((w, s, t))

class DisjointSets:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def _find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self._find(self.table[x])
			return self.table[x]

	def uniteSets(self, x, y):
		s1 = self._find(x)
		s2 = self._find(y)
		if s1 != s2:
			if self.table[s1] < self.table[s2]:
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2

	def isDisjoint(self, x, y):
		if self._find(x) != self._find(y):
			return True
		else:
			return False

def kruskal(vertices_num, edges):
	edges.sort(reverse=True)
	S = DisjointSets(vertices_num)
	weight = 0
	while edges:
		(w, s, t) = edges.pop()
		if S.isDisjoint(s, t):
			S.uniteSets(s, t)
			weight += w
	print(weight)
kruskal(v_num, E)


import sys

def kruskal(n: int, edges: list) -> int:
	tree = [-1] * n

	def get_root(x):
		if tree[x] < 0:
			return x
		tree[x] = get_root(tree[x])
		return tree[x]

	def unite(x, y):
		(x, y) = (get_root(x), get_root(y))
		if x != y:
			(big, small) = (x, y) if tree[x] < tree[y] else (y, x)
			tree[big] += tree[small]
			tree[small] = big
		return x != y
	return sum((w for ((w, _, _), _) in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n - 1))))
(V, E) = map(int, input().split())
edges = [(w, s, t) for (s, t, w) in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))


import heapq
(n, e) = map(int, input().split())
G = [[] for _ in range(n)]
for index in range(e):
	(s, t, w) = map(int, input().split())
	G[s].append([w, t])
	G[t].append([w, s])

def prim_heap():
	used = [True] * n
	edgelist = []
	for e in G[0]:
		heapq.heappush(edgelist, e)
	used[0] = False
	res = 0
	while len(edgelist) != 0:
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		for e in G[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, e)
		res += minedge[0]
	return res
ans = prim_heap()
print(ans)


from heapq import heapify
from heapq import heappop
from heapq import heappush

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
(V, E) = map(int, input().split())
uf = UnionFind(V)
hq = []
heapify(hq)
for i in range(E):
	(s, t, w) = map(int, input().split())
	heappush(hq, (w, s, t))
ans = 0
while len(hq) != 0:
	(w, s, t) = heappop(hq)
	if not uf.same(s, t):
		ans += w
		uf.union(s, t)
	else:
		continue
print(ans)


class UnionFind:

	def __init__(self, n):
		self.p = [i for i in range(n)]
		self.rank = [1] * n

	def root(self, x):
		if x == self.p[x]:
			return x
		self.p[x] = y = self.root(self.p[x])
		return y

	def unite(self, x, y):
		px = self.root(x)
		py = self.root(y)
		if px == py:
			return 0
		rx = self.rank[px]
		ry = self.rank[py]
		if ry < rx:
			self.p[py] = px
		elif rx < ry:
			self.p[px] = py
		else:
			self.p[py] = px
			self.rank[px] += 1
		return 1

	def same(self, x, y):
		px = self.root(x)
		py = self.root(y)
		return px == py
(V, E) = list(map(int, input().split()))
STW = sorted([list(map(int, input().split())) for _ in range(E)], key=lambda x: x[2])
union_find = UnionFind(V + 1)
ans = 0
for (s, t, w) in STW:
	if not union_find.same(s, t):
		ans += w
		union_find.unite(s, t)
print(ans)


class UnionFindTree:

	def __init__(self, n: int):
		self.__parent = [i for i in range(n)]
		self.__rank = [0 for i in range(n)]

	def unite(self, x, y) -> None:
		self.__link(self.__find_set(x), self.__find_set(y))

	def same(self, x, y) -> bool:
		return self.__find_set(x) == self.__find_set(y)

	def __find_set(self, x):
		if x != self.__parent[x]:
			self.__parent[x] = self.__find_set(self.__parent[x])
		return self.__parent[x]

	def __link(self, x, y):
		if self.__rank[x] < self.__rank[y]:
			self.__parent[x] = y
		else:
			if self.__rank[x] == self.__rank[y]:
				self.__rank[x] += 1
			self.__parent[y] = x

class Edge:

	def __init__(self, src, dst, weight):
		self.src = src
		self.dst = dst
		self.weight = weight
(V, E) = map(int, input().split())
INF = 10 ** 10
edges = [Edge(*map(int, input().split())) for i in range(E)]
edges.sort(key=lambda e: e.weight)
total_cost = 0
t = UnionFindTree(V)
for e in edges:
	if not t.same(e.src, e.dst):
		t.unite(e.src, e.dst)
		total_cost += e.weight
print(total_cost)


(num_V, num_E) = map(int, input().split())

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
root = []
for i in range(num_E):
	(s, t, w) = map(int, input().split())
	root.append((s, t, w))
root = sorted(root, key=lambda x: x[2])
uf = UnionFind(num_V)
ans = 0
for (s, t, w) in root:
	if uf.same(s, t):
		continue
	else:
		uf.union(s, t)
		ans += w
print(ans)


def kruskal():
	cost = 0
	edge.sort()
	for (c, u, v) in edge:
		if same(u, v):
			continue
		union(u, v)
		cost += c
	return cost

def find(x):
	if par[x] < 0:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def union(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return False
	if par[x] > par[y]:
		(x, y) = (y, x)
	par[x] += par[y]
	par[y] = x
	return True

def same(x, y):
	return find(x) == find(y)
(n, w) = map(int, input().split())
par = [-1] * n
edge = []
for _ in range(w):
	(x, y, z) = map(int, input().split())
	edge.append([z, x, y])
print(kruskal())


class UnionFind:

	def __init__(self, n):
		self.N = n
		self.parent = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]

	def root(self, x):
		visited_nodes = []
		while True:
			p = self.parent[x]
			if p == x:
				for node in visited_nodes:
					self.parent[node] = x
				return x
			else:
				visited_nodes.append(x)
				x = p

	def unite(self, x, y):
		if not self.root(x) == self.root(y):
			if self.rank[x] > self.rank[y]:
				self.parent[self.root(y)] = self.root(x)
			else:
				self.parent[self.root(x)] = self.root(y)
				if self.rank[x] == self.rank[y]:
					self.rank[self.root(y)] += 1

	def ifSame(self, x, y):
		return self.root(x) == self.root(y)

	def printDebugInfo(self):
		print([self.root(i) for i in range(self.N)])
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges.append([w, s, t])
edges.sort()
tree = UnionFind(V)
weight = 0
counter = 0
for edge in edges:
	if tree.ifSame(edge[1], edge[2]):
		continue
	else:
		tree.unite(edge[1], edge[2])
		weight += edge[0]
		counter += 1
	if counter == V - 1:
		break
print(weight)


from heapq import heappop, heappush
(v_num, e_num) = map(int, input().split())
pair_lst = [i for i in range(v_num)]
que = []
for _ in range(e_num):
	(s, t, w) = map(int, input().split())
	heappush(que, (w, s, t))

def find(x):
	if x == pair_lst[x]:
		return x
	else:
		tmp = find(pair_lst[x])
		pair_lst[x] = tmp
		return tmp
length_sum = 0
while que:
	(w, s, t) = heappop(que)
	root_s = find(s)
	root_t = find(t)
	if root_s != root_t:
		pair_lst[root_s] = root_t
		length_sum += w
print(length_sum)


import sys
input = sys.stdin.readline

def same_tree(node_a, node_b):
	if node_a.root() == node_b.root():
		return True

def unite(node_a, node_b):
	root_a = node_a.root()
	root_b = node_b.root()
	if root_a == root_b:
		return
	if root_b.depth > root_a.depth:
		(root_a, root_b) = (root_b, root_a)
	root_b.is_root = False
	root_b.parent = root_a
	root_a.depth = max(root_a.depth, root_b.depth + 1)

class Node:

	def __init__(self):
		self.is_root = True
		self.parent = None
		self.depth = 1

	def root(self):
		node = self
		while not node.is_root:
			node = node.parent
		return node

def main():
	(V, E) = map(int, input().split())
	nodes = [Node() for i in range(V)]
	stw = sorted([list(map(int, input().split())) for i in range(E)], key=lambda x: x[2])
	ans = 0
	for i in range(E):
		(s, t, w) = stw[i]
		if not same_tree(nodes[s], nodes[t]):
			unite(nodes[s], nodes[t])
			ans += w
	print(ans)
main()


import heapq
(v, e) = map(int, input().split())
ans = 0
par = [i for i in range(v)]
rank = [0] * v

def find(x, par):
	if par[x] == x:
		return par[x]
	else:
		return find(par[x], par)

def unite(x, y, par, rank):
	x = find(x, par)
	y = find(y, par)
	if rank[x] < rank[y]:
		par[x] = y
	else:
		par[y] = x
		if rank[x] == rank[y]:
			rank[x] += 1
L = []
for i in range(e):
	(a, b, d) = map(int, input().split())
	L.append([d, a, b])
L.sort()
for i in range(e):
	cur = heapq.heappop(L)
	if find(cur[1], par) != find(cur[2], par):
		ans += cur[0]
		unite(cur[1], cur[2], par, rank)
print(ans)


import sys
sys.setrecursionlimit(10000)

def root(x):
	if par[x] == x:
		return x
	else:
		par[x] = root(par[x])
		return par[x]

def unite(x, y):
	rx = root(x)
	ry = root(y)
	if rx != ry:
		par[rx] = ry

def same(x, y):
	return root(x) == root(y)
(n, m) = map(int, input().split())
E = []
for i in range(m):
	(s, t, w) = map(int, input().split())
	E.append([w, s, t])
E.sort()
par = [i for i in range(n)]
ans = 0
for e in E:
	if not same(e[1], e[2]):
		unite(e[1], e[2])
		ans += e[0]
print(ans)


import heapq

def find_root(x):
	if x == nodes[x]:
		return x
	else:
		root = nodes[x] = find_root(nodes[x])
		return root
(nv, ne) = map(int, input().split())
nodes = [i for i in range(nv)]
q = []
for _ in range(ne):
	(s, t, w) = map(int, input().split())
	heapq.heappush(q, (w, s, t))
sum = 0
while q:
	(w, s, t) = heapq.heappop(q)
	root_s = find_root(s)
	root_t = find_root(t)
	if root_s != root_t:
		nodes[root_s] = root_t
		sum += w
print(sum)


import heapq
(V, E) = map(int, input().split())
edges = [[] for _ in range(V)]
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges[s - 1].append([w, t - 1])
	edges[t - 1].append([w, s - 1])

def prim(n, w, edges):
	used = [True] * n
	edgelist = []
	for e in edges[0]:
		heapq.heappush(edgelist, e)
	used[0] = False
	res = 0
	while len(edgelist) != 0:
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		for e in edges[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, e)
		res += minedge[0]
	return res
print(prim(V, E, edges))


class Edge:

	def __init__(self, s, t, w):
		self.s = s
		self.t = t
		self.w = w

def union(x, y):
	x = findSet(x)
	y = findSet(y)
	link(x, y)

def link(x, y):
	if r[x] > r[y]:
		p[y] = x
	else:
		p[x] = y
		if r[x] == r[y]:
			r[y] = r[y] + 1

def findSet(x):
	if x != p[x]:
		p[x] = findSet(p[x])
	return p[x]

def same(x, y):
	return findSet(x) == findSet(y)
(p, r) = ([], [])
(n_V, n_E) = map(int, input().split())
for i in range(n_V):
	p.append(i)
	r.append(0)
Es = []
for _ in range(n_E):
	(s, t, w) = map(int, input().split())
	Es.append(Edge(s, t, w))
Es.sort(key=lambda e: e.w)
sum_w = 0
for e in Es:
	if not same(e.s, e.t):
		union(e.s, e.t)
		sum_w += e.w
print(sum_w)


def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def union(a, b):
	a = find(a)
	b = find(b)
	if a == b:
		return 0
	elif rank[a] > rank[b]:
		par[b] = a
	else:
		par[a] = b
		if rank[a] == rank[b]:
			rank[b] += 1

def same(a, b):
	return find(a) == find(b)

def Kruskal():
	cost = 0
	Edge.sort(key=lambda x: x[2])
	for i in range(E):
		(f, t, c) = Edge[i]
		if not same(f, t):
			union(f, t)
			cost += c
	return cost
(N, E) = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for _ in range(N)]
Edge = []
for i in range(E):
	(s, t, w) = map(int, input().split())
	Edge.append([s, t, w])
res = Kruskal()
print(res)


import heapq
(v, e) = map(int, input().split())
adj = [[] for _ in range(v)]
for _ in range(e):
	(a, b, c) = map(int, input().split())
	adj[a].append((b, c))
	adj[b].append((a, c))
visit = [0] * v
pq = []
for (next, w) in adj[0]:
	heapq.heappush(pq, (w, next))
visit[0] = 1
ans = 0
while pq:
	(w, next) = heapq.heappop(pq)
	if visit[next]:
		continue
	visit[next] = 1
	ans += w
	for (next, w) in adj[next]:
		if not visit[next]:
			heapq.heappush(pq, (w, next))
print(ans)


import sys

def kruskal(n: int, edges: list) -> int:
	tree = [-1] * n

	def get_root(x):
		if tree[x] < 0:
			return x
		tree[x] = get_root(tree[x])
		return tree[x]

	def unite(x, y):
		(x, y) = (get_root(x), get_root(y))
		if x != y:
			(big, small) = (x, y) if tree[x] < tree[y] else (y, x)
			tree[big] += tree[small]
			tree[small] = big
		return x != y
	cost = 0
	for ((w, _s, _t), _) in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n - 1)):
		cost += w
	return cost
(V, E) = map(int, input().split())
edges = [(w, s, t) for (s, t, w) in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))


(V_0, E_0) = map(int, input().split())
from collections import deque
V = [False] * V_0
V[0] = True
E = 0
import heapq
S = []
heapq.heapify(S)
graph = [[] for i in range(V_0)]
for e in range(E_0):
	(s, t, w) = map(int, input().split())
	graph[s].append((w, t))
	graph[t].append((w, s))
for (w, a) in graph[0]:
	heapq.heappush(S, (w, a))
while len(S) != 0:
	(w, a) = heapq.heappop(S)
	if V[a]:
		continue
	for (w2, b) in graph[a]:
		if not V[b]:
			heapq.heappush(S, (w2, b))
	V[a] = True
	E += w
print(E)


class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n

	def find(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parent[x] > self.parent[y]:
			(x, y) = (y, x)
		self.parent[x] += self.parent[y]
		self.parent[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.parent[self.find(x)]
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges.append((w, s, t))
edges.sort()
uf = UnionFind(V)
ans = 0
for edge in edges:
	if uf.same(edge[1], edge[2]):
		continue
	ans += edge[0]
	uf.unite(edge[1], edge[2])
print(ans)


(V, E) = map(int, input().split())
inf = float('inf')
graphs = [list(map(int, input().split())) for _ in range(E)]
graphs.sort(key=lambda x: x[2])
nodes = [i for i in range(V)]
cost = 0

def root(node):
	if nodes[node] == node:
		return node
	nodes[node] = root(nodes[node])
	return nodes[node]
for (i, j, k) in graphs:
	if not root(i) == root(j):
		cost += k
		nodes[root(i)] = root(j)
print(cost)


rank = {}
p = {}

class Edge:
	pass

def makeSet(x):
	p[x] = x
	rank[x] = 0

def link(x, y):
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
	if rank[x] == rank[y]:
		rank[y] += 1

def union(x, y):
	link(findSet(x), findSet(y))

def findSet(x):
	if x != p[x]:
		p[x] = findSet(p[x])
	return p[x]

def isSameSet(x, y):
	return findSet(x) == findSet(y)
(V, E) = map(int, input().split())
el = []
for i in range(E):
	(s, t, w) = map(int, input().split())
	e = Edge()
	e.source = s
	e.target = t
	e.weight = w
	el.append(e)

def kruskal(v, e):
	e = sorted(e, key=lambda x: x.weight)
	for i in v:
		makeSet(i)
	K = []
	for i in e:
		if findSet(i.source) != findSet(i.target):
			union(i.source, i.target)
			K.append(i.weight)
	return K
print(sum(kruskal(range(V), el)))


class DisjointSet:

	def __init__(self, size):
		self.rank = [None] * size
		self.p = [None] * size
		for i in range(size):
			self.make_set(i)
		return

	def make_set(self, x):
		self.p[x] = x
		self.rank[x] = 0
		return

	def same(self, x, y):
		return self.find_set(x) == self.find_set(y)

	def unite(self, x, y):
		self.link(self.find_set(x), self.find_set(y))
		return

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def find_set(self, x):
		if x != self.p[x]:
			self.p[x] = self.find_set(self.p[x])
		return self.p[x]

class Edge:

	def __init__(self, source, target, cost):
		self.source = source
		self.target = target
		self.cost = cost

def kruskal(edges):
	edges.sort(key=lambda x: x.cost)
	S = DisjointSet(n)
	K = []
	for i in range(m):
		if S.find_set(edges[i].source) != S.find_set(edges[i].target):
			K.append(edges[i])
			S.unite(edges[i].source, edges[i].target)
	return K
(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(s, t, w) = map(int, input().split())
	edges.append(Edge(s, t, w))
K = kruskal(edges)
cost = 0
while K:
	edge = K.pop()
	cost += edge.cost
print(cost)


from heapq import heappop, heappush
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(m):
	(u, v, c) = map(int, input().split())
	edge[u].append((c, v))
	edge[v].append((c, u))

def prim(s):
	d = [float('inf')] * n
	visited = [False] * n
	d[s] = 0
	visited[s] = True
	que = []
	for e in edge[s]:
		heappush(que, e)
	while que:
		(c, v) = heappop(que)
		if visited[v]:
			continue
		d[v] = c
		visited[v] = True
		for (cost, vtx) in edge[v]:
			if visited[vtx]:
				continue
			hq = (cost, vtx)
			heappush(que, hq)
	return d
print(sum(prim(0)))


class UnionFindTree:

	def __init__(self):
		self.p = {}
		self.rank = {}

	def make(self, x):
		self.p[x] = x
		self.rank[x] = 0

	def find(self, x):
		if x in self.p:
			if self.p[x] != x:
				self.p[x] = self.find(self.p[x])
			return self.p[x]
		return None

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		self._unite(self.find(x), self.find(y))

	def _unite(self, x, y):
		if self.rank[x] < self.rank[y]:
			self.p[x] = y
		else:
			self.p[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
(V, E) = map(int, input().split())
e = []
for i in range(E):
	(s, t, w) = map(int, input().split())
	e.append([w, s, t])
e.sort()
uft = UnionFindTree()
for i in range(V):
	uft.make(i)
ans = 0
for (w, s, t) in e:
	if not uft.same(s, t):
		uft.unite(s, t)
		ans += w
print(ans)


from heapq import heappop, heappush
inf = float('inf')
white = 0
gray = 1
black = 2

def prim():
	mindist[0] = 0
	PQ = [(0, 0)]
	while PQ:
		(minw, s) = heappop(PQ)
		color[s] = black
		if mindist[s] < minw:
			continue
		for (t, w) in G[s]:
			if color[t] == black:
				continue
			if w < mindist[t]:
				mindist[t] = w
				color[t] = gray
				heappush(PQ, (w, t))
	return sum(mindist)
(V, E) = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
	(s, t, w) = map(int, input().split())
	G[s].append((t, w))
	G[t].append((s, w))
color = [white] * V
mindist = [inf] * V
print(prim())


class UF:

	def __init__(self, n):
		self.parents = [-1] * n

	def find(self, n):
		if self.parents[n] < 0:
			return n
		else:
			self.parents[n] = self.find(self.parents[n])
			return self.parents[n]

	def union(self, u, v):
		(p1, p2) = (self.find(u), self.find(v))
		if p1 == p2:
			return
		if self.parents[p1] > self.parents[p2]:
			(p1, p2) = (p2, p1)
		self.parents[p1] += self.parents[p2]
		self.parents[p2] = p1

	def same(self, u, v):
		return self.find(u) == self.find(v)
(V, E) = map(int, input().split())
edges = []
for i in range(E):
	(s, t, w) = map(int, input().split())
	edges.append((w, s, t))
edges.sort(key=lambda x: x[0])
uf = UF(V)
ans = 0
for i in range(E):
	(w, s, t) = edges[i]
	if not uf.same(s, t):
		uf.union(s, t)
		ans += w
print(ans)


import sys, heapq
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 10

def I():
	return int(input())

def F():
	return float(input())

def S():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LS():
	return input().split()

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

def kruskal(es, V):
	es.sort(key=lambda x: x[2])
	uf = UnionFind(V)
	res = 0
	for e in es:
		if not uf.same(e[0], e[1]):
			uf.union(e[0], e[1])
			res += e[2]
	return res

def resolve():
	(V, E) = LI()
	es = [[[]] for _ in range(E)]
	for i in range(E):
		(s, t, w) = LI()
		es[i] = [s, t, w]
	print(kruskal(es, V))
resolve()


import heapq
(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(s, t, w) = map(int, input().split())
	heapq.heappush(edges, (w, s, t))
cost = 0
roots = [i for i in range(n)]
clusters = {i: {i} for i in range(n)}
while len(edges) > 0:
	(w, s, t) = heapq.heappop(edges)
	if roots[s] != roots[t]:
		cluster = clusters.pop(roots[t])
		for elem in cluster:
			roots[elem] = roots[s]
		clusters[roots[s]] |= cluster
		cost += w
print(cost)


import heapq
(v, e) = map(int, input().split())
edge = []
for i in range(e):
	(s, t, w) = map(int, input().split())
	edge.append([w, s, t])
heapq.heapify(edge)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.r = [i for i in range(n)]
		self.rank = [1 for i in range(n)]
		self.cost = 0

	def find(self, x):
		if x == self.r[x]:
			return x
		else:
			self.r[x] = self.find(self.r[x])
			return self.r[x]

	def union(self, x, y, c):
		rx = self.find(x)
		ry = self.find(y)
		if rx == ry:
			return
		if self.rank[ry] > self.rank[rx]:
			(rx, ry) = (ry, rx)
		self.r[ry] = rx
		self.rank[rx] += self.rank[ry]
		self.cost += c
uf = UnionFind(v)
while edge:
	path = heapq.heappop(edge)
	if uf.find(path[1]) == uf.find(path[2]):
		continue
	uf.union(path[1], path[2], path[0])
print(uf.cost)


import _heapq
inf = float('inf')

def prim():
	color = ['white' for _ in range(v)]
	D = [inf for _ in range(v)]
	M = [[] for _ in range(v)]
	for (s, t, w) in STW:
		M[s].append([w, t])
		M[t].append([w, s])
	queue = [[0, 0]]
	_heapq.heapify(queue)
	color[0] = 'gray'
	D[0] = 0
	while len(queue) > 0:
		num = _heapq.heappop(queue)[1]
		if color[num] == 'black':
			continue
		color[num] = 'black'
		for (i, j) in M[num]:
			if i < D[j] and color[j] != 'black':
				color[j] = 'gray'
				D[j] = i
				_heapq.heappush(queue, [i, j])
	return D
(v, e) = map(int, input().split())
STW = [list(map(int, input().split())) for _ in range(e)]
print(sum(prim()))


class Vertex:

	def __init__(self, p):
		self.p = p
		self.r = 0

class Edge:

	def __init__(self, s, t, w):
		self.s = s
		self.t = t
		self.w = w

def union(x, y):
	x = findSet(x)
	y = findSet(y)
	link(x, y)

def link(x, y):
	if V[x].r > V[y].r:
		V[y].p = x
	else:
		V[x].p = y
		if V[x].r == V[y].r:
			V[y].r = V[y].r + 1

def findSet(x):
	if x != V[x].p:
		V[x].p = findSet(V[x].p)
	return V[x].p

def same(x, y):
	return findSet(x) == findSet(y)
(n_V, n_E) = map(int, input().split())
V = []
for i in range(n_V):
	V.append(Vertex(i))
E = []
for _ in range(n_E):
	(s, t, w) = map(int, input().split())
	E.append(Edge(s, t, w))
E.sort(key=lambda e: e.w)
sum_w = 0
for e in E:
	if not same(e.s, e.t):
		union(e.s, e.t)
		sum_w += e.w
print(sum_w)


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.sizes = [0] * n

	def find(self, x):
		if x == self.par[x]:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			retrn
		if self.sizes[x] < self.sizes[y]:
			(x, y) = (y, x)
		self.par[y] = x
		self.sizes[x] += self.sizes[y]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, a):
		return sizes[self.find[x]]

class Edge:

	def __init__(self, s, t, w):
		self.s = s
		self.t = t
		self.w = w

	def __lt__(self, other):
		return self.w < other.w

def kruskal(edges, n):
	edges = sorted(edges)
	uf = UnionFind(n)
	min_cost = 0
	for edge in edges:
		if not uf.same(edge.s, edge.t):
			min_cost += edge.w
			uf.unite(edge.s, edge.t)
	return min_cost
(v, e) = map(int, input().split())
es = []
for i in range(e):
	(s, t, w) = map(int, input().split())
	es.append(Edge(s, t, w))
print(kruskal(es, v))


par = []
(V, E) = [int(s) for s in input().split()]
for i in range(V + 1):
	par.append(i)
graph = []
for _ in range(E):
	(x, y, w) = [int(s) for s in input().split()]
	graph.append((x, y, w))

def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def same(x, y):
	return find(x) == find(y)

def union(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		par[x] = y
graph = sorted(graph, key=lambda x: x[2])
ans = 0
for g in graph:
	if not same(g[0], g[1]):
		union(g[0], g[1])
		ans += g[2]
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n
		self.rank = [0] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.parents[y] += self.parents[x]
			self.parents[x] = y
		else:
			self.parents[x] += self.parents[y]
			self.parents[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def are_same(self, x, y):
		return self.find(x) == self.find(y)

	def element_count(self, x):
		x = self.find(x)
		return -self.parents[x]

	def group_count(self):
		count = 0
		for e in self.parents:
			if e < 0:
				count += 1
		return count

def kruskal(n, edges):
	u = UnionFind(n)
	ans = 0
	for x in edges:
		(s, t, w) = x
		if u.are_same(s, t) == False:
			u.union(s, t)
			ans += w
	return ans
from sys import stdin

def main():
	readline = stdin.readline
	(v, e) = map(int, readline().split())
	edges = [list(map(int, readline().split())) for _ in range(e)]
	edges.sort(key=lambda x: x[2])
	print(kruskal(v, edges))
main()


from operator import itemgetter
import sys
sys.setrecursionlimit(10000)

def inpl():
	return tuple(map(int, input().split()))
(V, E) = inpl()
edges = []
graph = [[] for _ in range(V)]
total_cost = 0
for _ in range(E):
	edges.append(inpl())
gw = itemgetter(2)
edges = sorted(edges, key=gw)
tree = [[-1, 1] for _ in range(V)]

def find(i):
	if tree[i][0] == -1:
		group = i
	else:
		group = find(tree[i][0])
	return group

def unite(x, y):
	px = find(x)
	py = find(y)
	if tree[px][1] == tree[py][1]:
		tree[py][0] = px
		tree[px][1] += 1
	else:
		if tree[px][1] < tree[py][1]:
			(px, py) = (py, px)
		tree[py][0] = px
for (s, t, w) in edges:
	if find(s) != find(t):
		unite(s, t)
		total_cost += w
		graph[s].append([t, w])
		graph[t].append([s, w])
print(total_cost)


from operator import itemgetter

class UnionFindTree:

	def __init__(self, size):
		self.rank = [0] * size
		self.p = [0] * size
		for i in range(size):
			self.makeSet(i)

	def makeSet(self, i):
		self.p[i] = i
		self.rank[i] = 0

	def same(self, x, y):
		return self.findSet(x) == self.findSet(y)

	def unite(self, x, y):
		self.link(self.findSet(x), self.findSet(y))

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def findSet(self, x):
		if x != self.p[x]:
			self.p[x] = self.findSet(self.p[x])
		return self.p[x]

	def print(self):
		print(self.p)

def readinput():
	(nv, ne) = list(map(int, input().split()))
	nList = []
	for _ in range(ne):
		(s, t, w) = list(map(int, input().split()))
		nList.append((s, t, w))
	return (nv, ne, nList)

def Kruskal(nv, nList):
	sortedList = sorted(nList, key=itemgetter(2))
	S = UnionFindTree(nv)
	K = []
	for e in sortedList:
		s = e[0]
		t = e[1]
		if S.same(s, t) == False:
			S.unite(s, t)
			K.append(e)
	return K

def main(nv, ne, nList):
	K = Kruskal(nv, nList)
	total = 0
	for e in K:
		total += e[2]
	return total
(nv, ne, nList) = readinput()
ans = main(nv, ne, nList)
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.parents[self.find(x)]

	def kruskal(self, edge):
		edge.sort()
		cost_sum = 0
		for (cost, node1, node2) in edge:
			if not self.same(node1, node2):
				cost_sum += cost
				self.union(node1, node2)
		return cost_sum

def resolve():
	(V, E) = map(int, input().split())
	edge = []
	for _ in range(E):
		(s, t, w) = map(int, input().split())
		edge.append([w, s, t])
	uf = UnionFind(V)
	res = uf.kruskal(edge)
	print(res)
resolve()


from heapq import heappush, heappop

class UnionFind:

	def __init__(self, n):
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[y] = x
(V, E) = map(int, input().split())
q = []
K = {}
ans = 0
S = UnionFind(V)
for _ in range(E):
	(s, t, w) = map(int, input().split())
	heappush(q, (w, s, t))
while len(q) > 0:
	(w, s, t) = heappop(q)
	if S.find(s) != S.find(t):
		ans += w
		S.union(s, t)
print(ans)


import sys
import time
input = sys.stdin.readline

def find(tree, x):
	idx = tree[x][0]
	if idx == x:
		return x
	else:
		root_idx = find(tree, idx)
		return root_idx

def unite(tree, x, y, w):
	x_root_idx = find(tree, x)
	y_root_idx = find(tree, y)
	if not x_root_idx == y_root_idx:
		if tree_rank[x_root_idx] < tree_rank[y_root_idx]:
			tree[x_root_idx] = (y_root_idx, w)
		else:
			tree[y_root_idx] = (x_root_idx, w)
			if tree_rank[x_root_idx] == tree_rank[y_root_idx]:
				tree_rank[x_root_idx] = tree_rank[x_root_idx] + 1

def same(tree, x, y):
	x_root_idx = find(tree, x)
	y_root_idx = find(tree, y)
	if x_root_idx == y_root_idx:
		return True
	else:
		return False
(v_num, e_num) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(e_num)]
union_find_tree = [(i, 0) for i in range(v_num)]
tree_rank = [0] * v_num
edges.sort(key=lambda x: x[2])
for e in edges:
	unite(union_find_tree, e[0], e[1], e[2])
print(sum((item[1] for item in union_find_tree)))


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parent = [i for i in range(self.n)]
		self.rank = [0] * self.n

	def find_root(self, x):
		if self.parent[x] == x:
			return x
		else:
			self.parent[x] = self.find_root(self.parent[x])
			return self.parent[x]

	def unite(self, x, y):
		rx = self.find_root(x)
		ry = self.find_root(y)
		if rx == ry:
			return
		if self.rank[rx] < self.rank[ry]:
			self.parent[rx] = ry
		else:
			self.parent[ry] = rx
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] += 1

	def is_same(self, x, y):
		return self.find_root(x) == self.find_root(y)
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges.append((w, s - 1, t - 1))
edges.sort()
uf = UnionFind(V)
total = 0
for e in edges:
	(w, s, t) = e
	if uf.is_same(s, t):
		continue
	uf.unite(s, t)
	total += w
print(total)


import sys
import collections
import heapq
import math
Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
(V, E) = map(int, sys.stdin.readline().split())
edges = collections.defaultdict(list)
for line in sys.stdin:
	e = Edge(*map(int, line.split()))
	edges[e.s].append(e)
	edges[e.t].append(Edge(e.t, e.s, e.cost))
heap = [(e.cost, e) for e in edges[0]]
heapq.heapify(heap)
nodes = {0}
min_cost = 0
while heap:
	(_, edge) = heapq.heappop(heap)
	if edge.t not in nodes:
		nodes.add(edge.t)
		for e in edges[edge.t]:
			heapq.heappush(heap, (e.cost, e))
		min_cost += edge.cost
print(min_cost)


import sys
from heapq import heappush, heappop, heapify
(V, E) = map(int, sys.stdin.readline().strip().split())
graph = [[] for _ in range(V)]
for _ in range(E):
	(s, t, w) = map(int, sys.stdin.readline().strip().split())
	graph[s].append((w, t))
	graph[t].append((w, s))
used = set()
q = []
for i in range(V):
	if len(graph[i]):
		for (w, t) in graph[i]:
			q.append((w, t))
		used.add(i)
		break
heapify(q)
ans = 0
while q:
	(w, s) = heappop(q)
	if s in used:
		continue
	used.add(s)
	ans += w
	for (w, t) in graph[s]:
		if t in used:
			continue
		heappush(q, (w, t))
print(ans)


import sys

def kruskal(v_count: int, edges: list) -> int:
	tree = [-1] * v_count

	def get_root(x):
		if tree[x] < 0:
			return x
		tree[x] = get_root(tree[x])
		return tree[x]

	def unite(x, y):
		(x, y) = (get_root(x), get_root(y))
		if x != y:
			(big, small) = (x, y) if tree[x] < tree[y] else (y, x)
			tree[big] += tree[small]
			tree[small] = big
		return x != y
	cost = 0
	for ((w, _s, _t), _) in zip(filter(lambda p: unite(*p[1:]), sorted(edges)), range(v_count - 1)):
		cost += w
	return cost
(V, E) = map(int, input().split())
edges = [(w, s, t) for (s, t, w) in (map(int, l.split()) for l in sys.stdin)]
print(kruskal(V, edges))


import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:

	def __init__(self, N):
		self.N = N
		self.parents = [-1] * N

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

def main():
	(V, E) = map(int, readline().split())
	L = []
	for _ in range(E):
		(s, t, w) = map(int, readline().split())
		L.append([s, t, w])
	L.sort(key=lambda x: x[2])
	uf = UnionFind(V)
	ans = 0
	for i in range(E):
		(s, t, w) = L[i]
		if not uf.same(s, t):
			uf.union(s, t)
			ans += w
	print(ans)
main()


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

class UF_tree:

	def __init__(self, n):
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		elif self.rank[x] < self.rank[y]:
			self.root[y] += self.root[x]
			self.root[x] = y
		else:
			self.root[x] += self.root[y]
			self.root[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def getNodeLen(self, x):
		return -self.root[self.find(x)]
(N, M) = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
edge.sort(key=lambda x: x[2])
ans = 0
uf = UF_tree(N)
for (s, t, c) in edge:
	if uf.isSame(s, t):
		continue
	ans += c
	uf.unite(s, t)
print(ans)


(n, m) = map(int, input().split())
stw = [list(map(int, input().split())) for _ in range(m)]
stw = sorted(stw, key=lambda x: x[2])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def Find_Root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.Find_Root(self.root[x])
			return self.root[x]

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return
		if self.root[x] > self.root[y]:
			(x, y) = (y, x)
		self.root[x] += self.root[y]
		self.root[y] = x

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return -self.root[self.Find_Root(x)]

	def Members(self, x):
		return [i for i in range(self.n) if self.Find_Root(i) == self.Find_Root(x)]

	def Roots(self):
		return [i for (i, x) in enumerate(self.root) if x < 0]

	def Group_Count(self):
		return len(self.Roots())

def kruskal():
	res = 0
	uf = UnionFind(n)
	for i in range(m):
		(s, t, w) = stw[i]
		if not uf.isSameGroup(s, t):
			uf.Unite(s, t)
			res += w
	return res
print(kruskal())


import array
import collections
import heapq
AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
INF = 2 ** 31 - 1
NO_VERTEX = -1

def compute_mst_prim(max_v, adj_list):
	pred = collections.defaultdict(lambda : NO_VERTEX)
	key = collections.defaultdict(lambda : INF)
	key[0] = 0
	pq = [(key[v], v) for v in range(max_v)]
	heapq.heapify(pq)
	in_pq = array.array('B', (True for _ in range(max_v)))
	while pq:
		(_, u) = heapq.heappop(pq)
		in_pq[u] = False
		for (v, v_cost) in adj_list[u]:
			if in_pq[v]:
				weight = v_cost
				if weight < key[v]:
					pred[v] = u
					key[v] = weight
					heapq.heappush(pq, (weight, v))
					in_pq[v] = True
	return (pred, key)

def main():
	(max_v, max_e) = map(int, input().split())
	adjacency_list = collections.defaultdict(set)
	for _ in range(max_e):
		(s, t, w) = map(int, input().split())
		adjacency_list[s].add(AdjacentVertex(t, w))
		adjacency_list[t].add(AdjacentVertex(s, w))
	(_, key) = compute_mst_prim(max_v, adjacency_list)
	print(sum(key.values()))
main()


rank = []
p = []

def makeSet(x):
	p.append(x)
	rank.append(0)

def union(x, y):
	link(findSet(x), findSet(y))

def link(x, y):
	if rank[x] > rank[y]:
		p[y] = x
	else:
		p[x] = y
		if rank[x] == rank[y]:
			rank[y] = rank[y] + 1

def findSet(x):
	if x != p[x]:
		p[x] = findSet(p[x])
	return p[x]

def same(x, y):
	return findSet(x) == findSet(y)

def kruskal(g):
	MST = 0
	edges = g
	for e in edges:
		u = e[0]
		v = e[1]
		if findSet(u) != findSet(v):
			union(u, v)
			MST += e[2]
	return MST
(V, E) = map(int, input().split())
G = [list(map(int, input().split())) for i in range(E)]
G.sort(key=lambda x: x[2])
for i in range(V):
	makeSet(i)
print(kruskal(G))


import sys
import collections
sys.setrecursionlimit(10 ** 7)

def init(n):
	return list(range(n + 1))

def find(lis, x):
	if lis[x] == x:
		return x
	else:
		lis[x] = find(lis, lis[x])
		return lis[x]

def sameset(lis, x, y):
	return find(lis, x) == find(lis, y)

def union(lis, x, y):
	x = find(lis, x)
	y = find(lis, y)
	if x != y:
		lis[x] = y
(V, E) = map(int, input().split())
union_find_tree = init(V)
graph = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	graph.append((s, t, w))
cost = 0
for (s, t, w) in sorted(graph, key=lambda x: x[2]):
	if not sameset(union_find_tree, s, t):
		union(union_find_tree, s, t)
		cost += w
print(cost)


import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x != y:
			if self.parent[x] > self.parent[y]:
				(x, y) = (y, x)
			self.parent[x] += self.parent[y]
			self.parent[y] = x

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

def kruskal(n, edges):
	sorted_edges = sorted(edges, key=itemgetter(2))
	uf = UnionFind(n)
	res = 0
	for (u, v, cost) in sorted_edges:
		if not uf.is_same(u, v):
			uf.merge(u, v)
			res += cost
	return res
(n, m) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
ans = kruskal(n, edges)
print(ans)


E = []
(v, e) = map(int, input().split())
for _ in range(e):
	(s, t, w) = map(int, input().split())
	E.append((w, s, t))

class UnionFind:

	def __init__(self, N):
		self.N = N
		self.parent = [-1] * N

	def findset(self, A):
		if self.parent[A] < 0:
			return A
		self.parent[A] = self.findset(self.parent[A])
		return self.parent[A]

	def size(self, A):
		return -self.parent[self.findset(A)]

	def unite(self, A, B):
		A = self.findset(A)
		B = self.findset(B)
		if A == B:
			return False
		if self.size(A) > self.size(B):
			(A, B) = (B, A)
		self.parent[A] += self.parent[B]
		self.parent[B] = A
		return True

	def is_same(self, A, B):
		return self.findset(A) == self.findset(B)

def kruskal(N):
	edges = sorted(E)
	ans = 0
	union = UnionFind(N)
	cnt = 0
	for (w, s, t) in edges:
		if cnt == N - 1:
			break
		if union.is_same(s, t):
			continue
		else:
			union.unite(s, t)
			ans += w
			cnt += 1
	return ans
print(kruskal(v))


from operator import itemgetter

class DisjointSet:

	def __init__(self, size):
		self.size = size
		self.rank = [None] * size
		self.parents = [None] * size
		for i in range(size):
			self.makeSet(i)

	def makeSet(self, x):
		self.parents[x] = x
		self.rank[x] = 0

	def findSet(self, x):
		if x != self.parents[x]:
			self.parents[x] = self.findSet(self.parents[x])
		return self.parents[x]

	def same(self, x, y):
		return self.findSet(x) == self.findSet(y)

	def unite(self, x, y):
		self.link(self.findSet(x), self.findSet(y))

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.parents[y] = x
		else:
			self.parents[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1
(n, m) = [int(s) for s in input().split()]
E = []
for _ in range(m):
	E.append([int(s) for s in input().split(' ')])

def kruskal(n, E):
	E = sorted(E, key=itemgetter(2))
	totalCost = 0
	S = DisjointSet(n)
	for (s, t, w) in E:
		if S.findSet(s) != S.findSet(t):
			S.unite(s, t)
			totalCost += w
	return totalCost
print(kruskal(n, E))


class UF:

	def __init__(self, n):
		self.N = n
		self.d = [-1] * n

	def size(self, a):
		x = self.root(a)
		return -self.d[x]

	def root(self, a):
		if self.d[a] < 0:
			return a
		else:
			self.d[a] = self.root(self.d[a])
			return self.d[a]

	def unite(self, a, b):
		x = self.root(a)
		y = self.root(b)
		if self.size(x) < self.size(y):
			(x, y) = (y, x)
		self.d[y] = x

	def same(self, a, b):
		return self.root(a) == self.root(b)

class Edge:

	def __init__(self, f, t, w):
		self.f = f
		self.t = t
		self.w = w

	def __lt__(self, other):
		return self.w < other.w

def kruskal(edges, n):
	uf = UF(n)
	sum = 0
	for e in sorted(edges):
		if not uf.same(e.f, e.t):
			uf.unite(e.f, e.t)
			sum += e.w
	return sum
(n, m) = map(int, input().split())
es = []
for i in range(m):
	(s, t, w) = map(int, input().split())
	es.append(Edge(s, t, w))
print(kruskal(es, n))


import sys
import heapq as hp
(WHITE, GRAY, BLACK) = (0, 1, 2)

def generate_adj_table(v_table):
	for each in v_table:
		(v_from, v_to, edge_weight) = map(int, each)
		init_adj_table[v_from][v_to] = edge_weight
		init_adj_table[v_to][v_from] = edge_weight
	return init_adj_table

def prim_span_tree():
	distance[init_v] = 0
	distance_heap = []
	hp.heappush(distance_heap, (0, init_v))
	while distance_heap:
		current_vertex = hp.heappop(distance_heap)[1]
		color[current_vertex] = BLACK
		for (adj_vertex, adj_weight) in adj_table[current_vertex].items():
			if color[adj_vertex] is not BLACK:
				if adj_weight < distance[adj_vertex]:
					distance[adj_vertex] = adj_weight
					parent[adj_vertex] = current_vertex
					color[adj_vertex] = GRAY
					hp.heappush(distance_heap, (adj_weight, adj_vertex))
	return distance
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
parent = [-1] * vertices
distance = [float('inf')] * vertices
color = [WHITE] * vertices
init_v = 0
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
print(sum(prim_span_tree()))


class DisjointSetElement:

	def __init__(self, x):
		self.parent = x
		self.rank = 0

class DisjointSet:

	def __init__(self, n):
		self.elems = [DisjointSetElement(n) for n in range(n)]

	def _find_set(self, x):
		if x != self.elems[x].parent:
			self.elems[x].parent = self._find_set(self.elems[x].parent)
		return self.elems[x].parent

	def same(self, x, y):
		return self._find_set(x) == self._find_set(y)

	def _link(self, x, y):
		if self.elems[x].rank > self.elems[y].rank:
			self.elems[y].parent = x
		else:
			self.elems[x].parent = y
			if self.elems[x].rank == self.elems[y].rank:
				self.elems[y].rank += 1

	def unite(self, x, y):
		self._link(self._find_set(x), self._find_set(y))

	def is_alone(self, x):
		return x == self.elems[x].parent

def read_inputs():
	(nv, ne) = [int(x) for x in input().split()]
	E = []
	for _ in range(ne):
		(s, t, w) = [int(x) for x in input().split()]
		E.append((w, s, t))
	return (nv, E)

def min_sp_tree(nv, E):
	K = DisjointSet(nv)
	total = 0
	n = 0
	i = iter(E)
	while n < nv - 1:
		(w, s, t) = next(i)
		if not K.same(s, t):
			K.unite(s, t)
			total += w
			n += 1
	return total

def main():
	(nv, E) = read_inputs()
	E.sort()
	print(min_sp_tree(nv, E))
main()


(par, rank) = ([], [])

def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		if rank[x] < rank[y]:
			par[x] = y
		else:
			par[y] = x
			if rank[x] == rank[y]:
				rank[x] += 1
(v, e) = map(int, input().split())
edge = []
for i in range(e):
	(s, t, w) = map(int, input().split())
	edge.append((w, s, t))
edge.sort()
mincost = 0
for i in range(v):
	par.append(i)
	rank.append(0)
for ee in edge:
	(w, s, t) = ee
	if find(s) != find(t):
		unite(s, t)
		mincost += w
print(mincost)


def ifcycle(e1, e2):
	while uf[e1] >= 0:
		e1 = uf[e1]
	while uf[e2] >= 0:
		e2 = uf[e2]
	if e1 == e2:
		return True
	if uf[e1] <= uf[e2]:
		uf[e1] += uf[e2]
		uf[e2] = e1
	else:
		uf[e2] += uf[e1]
		uf[e1] = e2
		return False
(x, y) = map(int, input().split())
a = []
uf = [-1] * x
for i in range(y):
	(v1, v2, v3) = map(int, input().split())
	a.append([v3, v1, v2])
a.sort()
ans = 0
cnt = 0
for p in range(y):
	(w, s, t) = a[p]
	if not ifcycle(s, t):
		ans += w
		cnt += 1
		if cnt >= x:
			print(w)
print(ans)


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 11
from heapq import heapify, heappush, heappop

def prim(n, G):
	ans = 0
	used = [0] * n
	used[0] = 1
	q = []
	for (e, c) in G[0]:
		heappush(q, (c, e))
	while len(q):
		(c1, e1) = heappop(q)
		if used[e1]:
			continue
		used[e1] = 1
		for (e2, c2) in G[e1]:
			if used[e2] == 0:
				heappush(q, (c2, e2))
		ans += c1
	return ans

def main():
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		G[a].append((b, c))
		G[b].append((a, c))
	ans = prim(n, G)
	print(ans)
main()


from collections import defaultdict
import heapq
(V, E) = map(int, input().split())
edges = defaultdict(list)
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges[s].append((t, w))
	edges[t].append((s, w))
in_tree = [False] * V
ans = 0
start = 0
in_tree[start] = True
q = [(w, start, t) for (t, w) in edges[start]]
heapq.heapify(q)
while q:
	(w, s, t) = heapq.heappop(q)
	if in_tree[s] == in_tree[t]:
		continue
	ans += w
	in_tree[t] = True
	for (tt, w) in edges[t]:
		heapq.heappush(q, (w, t, tt))
print(ans)


class UnionFind:

	def __init__(self, V):
		self.group = [i for i in range(V)]
		self.rank = [0] * V

	def find(self, x):
		if x != self.group[x]:
			self.group[x] = self.find(self.group[x])
		return self.group[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.group[x] = y
		else:
			self.group[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def is_same_group(self, x, y):
		return self.find(x) == self.find(y)

class Edge:

	def __init__(self, FROM, TO, WEIGHT):
		self.FROM = FROM
		self.TO = TO
		self.WEIGHT = WEIGHT

	def __lt__(self, arg):
		return self.WEIGHT < arg.WEIGHT
(V, E) = map(int, input().split())
UF = UnionFind(V)
G = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	G.append(Edge(s, t, w))
G = sorted(G)
ans = 0
for i in range(E):
	if UF.is_same_group(G[i].FROM, G[i].TO):
		continue
	UF.unite(G[i].FROM, G[i].TO)
	ans += G[i].WEIGHT
print(ans)


from heapq import heappush, heappop
import sys

class PriorityQueue:

	def __init__(self):
		self._queue = []

	def push(self, value):
		heappush(self._queue, value)

	def pop(self):
		return heappop(self._queue)

	@property
	def empty(self):
		return not self._queue

	def __len__(self):
		return len(self._queue)

	def __contains__(self, item):
		return item in self._queue
(v, e) = map(int, input().split())
if v == 1:
	print(0)
	sys.exit()
edge = [[] for _ in range(v)]
for _ in range(e):
	(s, t, w) = map(int, input().split())
	edge[s].append((w, t))
	edge[t].append((w, s))
V = set()
pq = PriorityQueue()
weight = 0
V.add(0)
for i in edge[0]:
	pq.push(i)
while True:
	(nw, nv) = pq.pop()
	if nv in V:
		continue
	else:
		weight += nw
		V.add(nv)
		for i in edge[nv]:
			pq.push(i)
	if len(V) == v:
		break
print(weight)


import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10 ** 30
G = []
E = []

class UnionFind:

	def __init__(self, n):
		self.rank = [0] * n
		self.parent = [0] * n
		self.make(n)

	def make(self, n):
		for i in range(n):
			self.parent[i] = i

	def unite(self, x, y):
		xroot = self.findset(x)
		yroot = self.findset(y)
		if self.rank[xroot] < self.rank[yroot]:
			self.parent[xroot] = yroot
		elif self.rank[xroot] > self.rank[yroot]:
			self.parent[yroot] = xroot
		else:
			self.parent[xroot] = yroot
			self.rank[yroot] += 1
			node = y
			while True:
				self.rank[node] += 1
				if self.parent[node] == node:
					break
				node = self.parent[node]
			self.rank[y] += 1

	def findset(self, x):
		if self.parent[x] == x:
			return x
		else:
			root = self.findset(self.parent[x])
			self.parent[x] = root
			return root

class Edge:

	def __init__(self, fr, to, w):
		self.fr = fr
		self.to = to
		self.w = w

def kruskal(v, e):
	global E
	E.sort(key=lambda x: x.w)
	uf = UnionFind(v)
	mst = []
	for i in range(e):
		if uf.findset(E[i].fr) != uf.findset(E[i].to):
			uf.unite(E[i].fr, E[i].to)
			mst.append(E[i])
	return mst

def main():
	global G, E
	(n, e) = map(int, input().strip().split())
	G = [[] for _ in range(n)]
	E = [0] * e
	for i in range(e):
		(s, t, w) = map(int, input().strip().split())
		E[i] = Edge(s, t, w)
	mst = kruskal(n, e)
	ans = 0
	for q in mst:
		ans += q.w
	print(ans)
main()


def root(x):
	if parent_map[x] == x:
		return x
	parent_map[x] = root(parent_map[x])
	return parent_map[x]

def same(x, y):
	return root(x) == root(y)

def unite(x, y):
	x = root(x)
	y = root(y)
	parent_map[x] = y
(v, e) = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(e)]
edges.sort(key=lambda x: x[2])
parent_map = [i for i in range(v)]
result = 0
for (s, t, w) in edges:
	if not same(s, t):
		result += w
		unite(s, t)
print(result)


import sys

class UnionFind:

	def __init__(self, node_size):
		self._node = node_size
		self.par = [i for i in range(self._node)]
		self.rank = [0] * self._node

	def find(self, ver):
		if self.par[ver] == ver:
			return ver
		else:
			self.par[ver] = self.find(self.par[ver])
			return self.par[ver]

	def unite(self, ver1, ver2):
		(ver1, ver2) = (self.find(ver1), self.find(ver2))
		if ver1 == ver2:
			return
		if self.rank[ver1] < self.rank[ver2]:
			(ver1, ver2) = (ver2, ver1)
		self.par[ver2] = ver1
		if self.rank[ver1] == self.rank[ver2]:
			self.rank[ver1] += 1

	def same(self, ver1, ver2):
		return self.find(ver1) == self.find(ver2)

class Kruskal:

	class Edge:

		def __init__(self, u, v, cost):
			(self.u, self.v, self.cost) = (u, v, cost)

		def __lt__(self, another):
			return self.cost < another.cost

	def __init__(self, node_size):
		self._node = node_size
		self._edge_list = []

	def add_edge(self, u, v, cost):
		self._edge_list.append(self.Edge(u, v, cost))

	def solve(self):
		uf = UnionFind(self._node)
		res = 0
		self._edge_list.sort()
		for e in self._edge_list:
			if not uf.same(e.u, e.v):
				uf.unite(e.u, e.v)
				res += e.cost
		return res
(n, m) = map(int, sys.stdin.readline().split())
kr = Kruskal(n)
for _ in range(m):
	(s, t, w) = map(int, sys.stdin.readline().split())
	kr.add_edge(s, t, w)
print(kr.solve())


from collections import defaultdict
from heapq import heappush, heappop
(v, e) = map(int, input().split())
E = defaultdict(list)
for _ in range(e):
	(s, t, w) = map(int, input().split())
	E[s].append((w, t))
	E[t].append((w, s))
d = [float('inf')] * v
used = [False] * v
d[0] = 0
ans = 0
q = []
heappush(q, (0, 0))
while q:
	(dist, now) = heappop(q)
	if used[now]:
		continue
	used[now] = True
	ans += dist
	for (w, nxt) in E[now]:
		if not used[nxt]:
			heappush(q, (w, nxt))
print(ans)


import heapq

def prim_heap(v):
	used = [True] * v
	edgelist = []
	for e in edge[0]:
		heapq.heappush(edgelist, e)
	used[0] = False
	res = 0
	while len(edgelist) != 0:
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, e)
		res += minedge[0]
	return res
(v, e) = map(int, input().split())
edge = [[] for _ in range(v)]
for i in range(e):
	(s, t, w) = map(int, input().split())
	edge[s].append((w, t))
	edge[t].append((w, s))
print(prim_heap(v))


import array
import collections
import heapq
AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
INF = 2 ** 31 - 1
NO_VERTEX = -1

def compute_mst_prim(max_v, adj_list):
	pred = collections.defaultdict(lambda : NO_VERTEX)
	key = collections.defaultdict(lambda : INF)
	key[0] = 0
	pq = [(key[v], v) for v in range(max_v)]
	heapq.heapify(pq)
	in_pq = array.array('B', (True for _ in range(max_v)))
	while pq:
		(_, u) = heapq.heappop(pq)
		in_pq[u] = False
		for (v, v_cost) in adj_list[u]:
			if in_pq[v]:
				weight = v_cost
				if weight < key[v]:
					pred[v] = u
					key[v] = weight
					heapq.heappush(pq, (weight, v))
					in_pq[v] = True
	return (pred, key)
(max_v, max_e) = map(int, input().split())
adjacency_list = collections.defaultdict(set)
for _ in range(max_e):
	(s, t, w) = map(int, input().split())
	adjacency_list[s].add(AdjacentVertex(t, w))
	adjacency_list[t].add(AdjacentVertex(s, w))
(_, key) = compute_mst_prim(max_v, adjacency_list)
print(sum(key.values()))


class UnionFind(object):

	def __init__(self, n):
		self.parent = {i: i for i in range(1, n + 1)}
		self.size = {i: 1 for i in range(1, n + 1)}

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def getsize(self, a):
		return self.size[self.find(a)]

	def unite(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] > self.size[b]:
			self.size[a] += self.size[b]
			self.parent[b] = a
		else:
			self.size[b] += self.size[a]
			self.parent[a] = b

	def isunited(self, a, b):
		return self.find(a) == self.find(b)
(V, E) = map(int, input().split())
uft = UnionFind(V)
l = [tuple(map(int, input().split())) for _ in range(E)]
l.sort(key=lambda x: x[2])
ans = 0
for (s, t, w) in l:
	s += 1
	t += 1
	if not uft.isunited(s, t):
		ans += w
		uft.unite(s, t)
print(ans)


import heapq
from itertools import accumulate
(v, e) = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
	(s, t, d) = map(int, input().split())
	g[s].append((d, t))
	g[t].append((d, s))
visitedv = [False] * v
visitedv[0] = True
visitede = 0
candidate = []
for i in g[0]:
	heapq.heappush(candidate, i)
while len(candidate):
	minedge = heapq.heappop(candidate)
	if visitedv[minedge[1]]:
		continue
	c = minedge[1]
	visitedv[c] = True
	visitede += minedge[0]
	for i in g[c]:
		if not visitedv[i[1]]:
			heapq.heappush(candidate, i)
print(visitede)


import sys

class UnionFind:

	def __init__(self, nvertices):
		self.rank = [1] * (nvertices + 5)
		self.p = [i for i in range(nvertices + 5)]

	def find_set(self, u):
		if u != self.p[u]:
			self.p[u] = self.find_set(self.p[u])
		return self.p[u]

	def unite(self, u, v):
		x = self.find_set(u)
		y = self.find_set(v)
		if x == y:
			return
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def is_connected(self, u, v):
		return self.find_set(u) == self.find_set(v)

def main():
	sys.setrecursionlimit(int(100000.0))
	(nvertices, nedges) = map(int, input().split())
	edges = []
	for i in range(nedges):
		(u, v, w) = map(int, input().split())
		edges.append((w, u, v))
	edges.sort(key=lambda e: e[0])
	ans = 0
	uf = UnionFind(nvertices)
	for (w, u, v) in edges:
		if not uf.is_connected(u, v):
			uf.unite(u, v)
			ans += w
	print(ans)
main()


def kruskal(g, size):
	g.sort(key=itemgetter(2), reverse=True)
	uf = union_find(size)
	tree = []
	while len(tree) < size - 1:
		(u, v, d) = g.pop()
		if not uf.union(u, v):
			tree.append((u, v, d))
	return tree

class union_find:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return True
		if self.table[y] < self.table[x]:
			(x, y) = (y, x)
		self.table[x] += self.table[y]
		self.table[y] = x
		return False

	def find(self, x):
		if self.table[x] < 0:
			return x
		self.table[x] = self.find(self.table[x])
		return self.table[x]
from sys import stdin
from operator import itemgetter
import heapq
readline = stdin.readline
(v, e) = map(int, readline().split())
g = [list(map(int, readline().split())) for _ in range(e)]
tree = kruskal(g, v)
print(sum((d for (s, t, d) in tree)))


from heapq import heappush, heappop, heapify

def prim(n, graph):
	used = [False] * n
	hq = [(w, v) for (v, w) in graph[0]]
	heapify(hq)
	used[0] = True
	res = 0
	while hq:
		(w, v) = heappop(hq)
		if used[v]:
			continue
		used[v] = True
		res += w
		for (cv, cw) in graph[v]:
			if used[cv]:
				continue
			heappush(hq, (cw, cv))
	return res
(V, E) = map(int, input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
	(s, t, w) = map(int, input().split())
	graph[s].append((t, w))
	graph[t].append((s, w))
print(prim(V, graph))


class Edge:

	def __init__(self, u, v, cost):
		self.u = u
		self.v = v
		self.cost = cost

	def __str__(self):
		return 'u: ' + str(self.u) + ' v: ' + str(self.v) + ' cost: ' + str(self.cost)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

def solve():
	(V, E) = map(int, input().split())
	edges = []
	for i in range(E):
		(s, t, w) = map(int, input().split())
		e = Edge(s, t, w)
		edges.append(e)
	edges.sort(key=lambda e: e.cost)
	uf = UnionFind(V + 1)
	ans = 0
	for edge in edges:
		if not uf.isSame(edge.u, edge.v):
			uf.unite(edge.u, edge.v)
			ans += edge.cost
	print(ans)
solve()


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)
(V, E) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(E)]
X = sorted(X, key=lambda x: x[2])
UF = UnionFind(V)
ans = 0
for i in range(E):
	(a, b) = (X[i][0] + 1, X[i][1] + 1)
	if not UF.same_check(a, b):
		UF.union(a, b)
		ans += X[i][2]
print(ans)


import sys
sys.setrecursionlimit(100000)

def find(x, S):
	if S[x] == x:
		return x
	else:
		S[x] = find(S[x], S)
		return S[x]

def same(x, y, S):
	return find(x, S) == find(y, S)

def unite(x, y, S):
	rx = find(x, S)
	ry = find(y, S)
	if rx == ry:
		return None
	else:
		S[rx] = ry
[V, E] = [int(i) for i in input().split()]
S = [i for i in range(V)]
edges = []
ans = 0
for i in range(E):
	edges.append([int(i) for i in input().split()])
for (s, t, w) in sorted(edges, key=lambda x: x[2]):
	if same(s, t, S):
		continue
	else:
		unite(s, t, S)
		ans += w
print(ans)


from sys import setrecursionlimit

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def check(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def count_group(self, n):
		return len({self.find(x) for x in range(1, n + 1)})
(v, e) = map(int, input().split())
stw = [list(map(int, input().split())) for i in range(e)]
stw.sort(key=lambda x: x[-1])
uf = UnionFind(v)
rec = 0
for (s, t, w) in stw:
	if not uf.check(s, t):
		uf.union(s, t)
		rec += w
print(rec)


import sys
readline = sys.stdin.readline
from operator import itemgetter

class UnionFind:
	__slots__ = ['p', 'rank']

	def __init__(self, n):
		self.p = list(range(n))
		self.rank = [0] * n

	def find_root(self, x):
		if x != self.p[x]:
			self.p[x] = self.find_root(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def unite(self, x, y):
		u = self.find_root(x)
		v = self.find_root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
		else:
			self.p[v] = u
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
(n, m) = map(int, readline().split())
edges = [tuple(map(int, readline().split())) for _ in [0] * m]
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
	while edges:
		(s, t, w) = edges.pop()
		if not uf.same(s, t):
			uf.unite(s, t)
			break
	ans += w
print(ans)


import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop, heapify

def prim(V, E, v=0):
	visited = [False] * V
	visited[v] = True
	count = V - 1
	dist = [float('inf')] * V
	dist[v] = 0
	q = list(E[v])
	heapify(q)
	for (c, u) in E[v]:
		dist[u] = c
	while count and q:
		(c, v) = heappop(q)
		if visited[v]:
			continue
		visited[v] = True
		count -= 1
		for (c, u) in E[v]:
			if visited[u]:
				continue
			dist[u] = min(dist[u], c)
			heappush(q, (dist[u], u))
	return dist

def main():
	(V, e) = map(int, input().split())
	E = [[] for i in range(V)]
	for i in range(e):
		(v, u, c) = map(int, input().split())
		E[v].append((c, u))
		E[u].append((c, v))
(V, e) = map(int, input().split())
E = deque((deque() for i in range(V)))
for i in range(e):
	(v, u, c) = map(int, input().split())
	E[v].append((c, u))
	E[u].append((c, v))
print(sum(prim(V, E)))


from collections import defaultdict
import heapq
(vertices, edges) = map(int, input().split(' '))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float('inf')] * vertices
for e in range(edges):
	(source, target, w) = map(int, input().split(' '))
	link[source] = link.get(source, set()) | {target}
	link[target] = link.get(target, set()) | {source}
	weight[source].update({target: w})
	weight[target].update({source: w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue, [0, 0])
went = [0] * vertices
now_weight = 0
way[0] = 0
while queue:
	(here_weight, here) = heapq.heappop(queue)
	if went[here]:
		continue
	went[here] = 1
	now_weight += here_weight
	(min_weight, next_t) = (float('inf'), -1)
	for c in link[here]:
		if not went[c] and way[c] > weight[here][c]:
			heapq.heappush(queue, [weight[here][c], c])
			way[c] = weight[here][c]
print(now_weight)


(V, E) = list(map(int, input().split()))
weight = []
for i in range(E):
	(s, t, w) = list(map(int, input().split()))
	weight.append((s, t, w))
weight.sort(key=lambda x: x[2])
parent = [i for i in range(V)]
rank = [0 for i in range(V)]

def find(x):
	if parent[x] == x:
		return x
	else:
		return find(parent[x])

def union(x, y):
	a = find(x)
	b = find(y)
	if rank[a] < rank[b]:
		parent[a] = b
	else:
		parent[b] = a
		if rank[a] == rank[b]:
			rank[a] += 1
sum_weight = 0
for i in range(E):
	(a, b, c) = weight[i]
	if find(a) != find(b):
		union(a, b)
		sum_weight += c
	else:
		continue
print(sum_weight)


import sys
import queue
sys.setrecursionlimit(10 ** 6)

class UnionFind:

	def __init__(self, n):
		self.parents = [-1] * n
		self.rank = [0] * n

	def root(self, x):
		if self.parents[x] == -1:
			return x
		self.parents[x] = self.root(self.parents[x])
		return self.parents[x]

	def unite(self, x, y):
		x_root = self.root(x)
		y_root = self.root(y)
		if x_root == y_root:
			return
		if self.rank[x_root] < self.rank[y_root]:
			self.parents[x_root] = y_root
		elif self.rank[x_root] == self.rank[y_root]:
			self.parents[x_root] = y_root
			self.rank[y_root] += 1
		else:
			self.parents[y_root] = x_root
		return

	def is_in_same(self, x, y):
		if self.root(x) == self.root(y):
			return True
		else:
			return False

def main():
	(v, e) = map(int, sys.stdin.readline().strip().split())
	edges = []
	for _ in range(e):
		(s, t, w) = map(int, sys.stdin.readline().strip().split())
		edges.append((s, t, w))
	edges = sorted(edges, key=lambda x: x[2])
	ans = 0
	unionfind = UnionFind(v)
	for (s, t, w) in edges:
		if unionfind.is_in_same(s, t):
			continue
		else:
			unionfind.unite(s, t)
			ans += w
	print(ans)
main()


import sys
iim = lambda : map(int, sys.stdin.readline().rstrip().split())

def resolve():
	it = map(int, sys.stdin.read().split())
	(V, E) = (next(it), next(it))
	ee = [-1] * V

	def find(a):
		q = []
		while ee[a] >= 0:
			q.append(a)
			a = ee[a]
		for i in q:
			ee[i] = a
		return a

	def union(a, b):
		ai = find(a)
		bi = find(b)
		(r1, r2) = (ee[ai], ee[bi])
		if r1 > r2:
			(ai, bi) = (bi, ai)
		ee[bi] = ai
		if r1 == r2:
			ee[ai] -= 1

	def same(a, b):
		ai = find(a)
		bi = find(b)
		return ai == bi
	ans = 0
	for (si, ti, wi) in sorted(zip(it, it, it), key=lambda x: x[2]):
		if same(si, ti):
			continue
		ans += wi
		union(si, ti)
	print(ans)
resolve()


from heapq import heappop, heappush
(nv, ne) = map(int, input().split())
pair_lst = [i for i in range(nv)]
que = []
for i in range(ne):
	(si, ti, wi) = map(int, input().split())
	heappush(que, (wi, si, ti))

def find(x):
	if x == pair_lst[x]:
		return x
	else:
		tmp = find(pair_lst[x])
		pair_lst[x] = tmp
		return tmp
length_sum = 0
while que:
	(w, s, t) = heappop(que)
	root_s = find(s)
	root_t = find(t)
	if root_s != root_t:
		pair_lst[root_s] = root_t
		length_sum += w
print(length_sum)


import heapq

def prim_heap():
	used = [True] * n
	edgelist = []
	for e in edge[0]:
		heapq.heappush(edgelist, e)
	used[0] = False
	res = 0
	while len(edgelist) != 0:
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, e)
		res += minedge[0]
	return res
(n, w) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(w):
	(x, y, z) = map(int, input().split())
	edge[x].append([z, y])
	edge[y].append([z, x])
print(prim_heap())


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parent = [i for i in range(n)]
		self.rank = [1] * n
		self.size = [1] * n

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.parent[x] = y
				self.size[y] += self.size[x]
			else:
				self.parent[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def group_size(self, x):
		return self.size[self.find(x)]

def kruskal(max_vertex, edges):
	edges.sort(key=lambda x: x[2])
	uf = UnionFind(max_vertex)
	mst = []
	for edge_cost in edges:
		(es, ee, cost) = edge_cost
		if not uf.is_same(es, ee):
			uf.unite(es, ee)
			mst.append([(es, ee), cost])
	return mst
(v, e) = map(int, input().split())
graph = []
for i in range(e):
	(f, s, cost) = map(int, input().split())
	graph.append([f, s, cost])
ans = 0
for i in kruskal(v, graph):
	ans += i[1]
print(ans)


import heapq

def prim():
	used = [1] * n
	used[0] = 0
	lis = []
	res = 0
	for q in edge[0]:
		heapq.heappush(lis, q)
	while lis:
		minedge = heapq.heappop(lis)
		if used[minedge[1]] == 0:
			continue
		v = minedge[1]
		used[v] = 0
		for q in edge[v]:
			if used[q[1]] == 1:
				heapq.heappush(lis, q)
		res += minedge[0]
	return res
(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(ad, b, c) = map(int, input().split())
	edge[ad].append([c, b])
	edge[b].append([c, ad])
print(prim())


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
		return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def nums(self, x):
		return abs(self.parents[self.find(x)])

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
(N, M) = map(int, input().split())
edges = [] * M
for i in range(M):
	(a, b, w) = map(int, input().split())
	edges.append((w, a, b))
edges.sort()
uf = UnionFind(N)
ans = 0
for i in range(M):
	(u, x, y) = edges[i]
	if not uf.same(x, y):
		uf.union(x, y)
		ans += u
print(ans)


class UnionFind:

	def __init__(self, v):
		self.rank = [1] * v
		self.par = [x for x in range(v)]

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		if self.find(x) == self.find(y):
			return False
		else:
			p_x = self.find(x)
			p_y = self.find(y)
			if self.rank[p_x] >= self.rank[p_y]:
				self.par[p_y] = p_x
				self.rank[p_y] += 1
			else:
				self.par[p_x] = p_y
				self.rank[p_x] += 1

	def same(self, x, y):
		p_x = self.find(x)
		p_y = self.find(y)
		return p_x == p_y
(v, e) = map(int, input().split())
e_l = [[int(x) for x in input().split()] for y in range(e)]
e_l.sort(key=lambda x: x[2])

def Kruskal(s):
	ans = 0
	uf = UnionFind(v)
	for (_s, _t, _w) in e_l:
		if not uf.same(_s, _t):
			uf.unite(_s, _t)
			ans += _w
	return ans
print(Kruskal(0))


import sys
sys.setrecursionlimit(10 ** 8)

def ii():
	return int(sys.stdin.readline())

def mi():
	return map(int, sys.stdin.readline().split())

def li():
	return list(map(int, sys.stdin.readline().split()))

def li2(N):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def dp2(ini, i, j):
	return [[ini] * i for _ in range(j)]

def dp3(ini, i, j, k):
	return [[[ini] * i for _ in range(j)] for _ in range(k)]

class UnionFind:

	def __init__(self, n):
		self.d = [-1] * n

	def find(self, x):
		if self.d[x] < 0:
			return x
		else:
			self.d[x] = self.find(self.d[x])
			return self.find(self.d[x])

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		if self.d[x] > self.d[y]:
			(x, y) = (y, x)
		self.d[x] += self.d[y]
		self.d[y] = x
		return True

	def same(self, x, y):
		if self.find(x) == self.find(y):
			return True
		return False

	def size(self, x):
		return -1 * self.d[self.find(x)]
(V, E) = mi()
stw = li2(E)
stw.sort(key=lambda x: x[2])
T = UnionFind(V)
cnt = 0
for i in range(E):
	(s, t, w) = (stw[i][0], stw[i][1], stw[i][2])
	if not T.same(s, t):
		T.unite(s, t)
		cnt += w
print(cnt)


from sys import stdin
input = stdin.readline
from collections import defaultdict
MAX = 10000
infty = -1

class Disjoint:

	def __init__():
		return

def getRoot(x):
	global v
	for _ in range(v + 1):
		if dic[x]['parent'] == x:
			return x
		x = dic[x]['parent']

def unite(x, y):
	r = getRoot(x)
	l = getRoot(y)
	a = dic[r]['rank']
	b = dic[l]['rank']
	if a == b:
		dic[r]['rank'] += 1
		dic[l]['parent'] = r
	elif a > b:
		dic[l]['rank'] = 0
		dic[l]['parent'] = r
	elif a < b:
		dic[r]['rank'] = 0
		dic[r]['parent'] = l
lines = stdin.readlines()
dic = defaultdict()
(v, e) = map(int, lines[0].split())
E = [list(map(int, lines[i + 1].split())) for i in range(e)]
E = sorted(E, key=lambda x: x[2])
E = sorted(E, key=lambda x: x[2])
for _ in range(v):
	dic[_] = {'rank': 0, 'parent': _}
k = 0
total = 0
for edge in E:
	if getRoot(edge[0]) != getRoot(edge[1]):
		unite(edge[0], edge[1])
		k += 1
		total += edge[2]
print(total)


import sys

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def main():
	(V, E) = map(int, input().split())
	uf = UnionFind(V)
	edges = []
	for _ in range(E):
		(s, t, w) = map(int, input().split())
		edges.append((w, s, t))
	edges.sort()
	cost = 0
	for edge in edges:
		(w, s, t) = edge
		if not uf.same(s, t):
			cost += w
			uf.union(s, t)
	print(cost)
	return
main()


import sys
import heapq as hp
(WHITE, GRAY, BLACK) = (0, 1, 2)

def generate_adj_table(v_table):
	for each in v_table:
		(v_from, v_to, edge_weight) = map(int, each)
		init_adj_table[v_from][v_to] = edge_weight
		init_adj_table[v_to][v_from] = edge_weight
	return init_adj_table

def prim_span_tree():
	distance[init_v] = 0
	parent[init_v] = -1
	path_heap = []
	hp.heappush(path_heap, (distance[init_v], init_v))
	while len(path_heap) >= 1:
		current_vertex = hp.heappop(path_heap)[1]
		color[current_vertex] = BLACK
		for (adj_vertex, adj_weight) in adj_table[current_vertex].items():
			if color[adj_vertex] is not BLACK:
				if adj_weight < distance[adj_vertex]:
					distance[adj_vertex] = adj_weight
					parent[adj_vertex] = current_vertex
					color[adj_vertex] = GRAY
					hp.heappush(path_heap, (distance[adj_vertex], adj_vertex))
	return distance
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
parent = [-1] * vertices
distance = [float('inf')] * vertices
color = [WHITE] * vertices
init_v = 0
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
print(sum(prim_span_tree()))


import heapq as pq
(n, E) = map(int, input().split())
M = [[] for i in range(n)]
for i in range(E):
	(s, t, w) = map(int, input().split())
	M[s].append([t, w])
	M[t].append([s, w])

def prim():
	color = [0] * n
	d = [float('inf')] * n
	d[0] = 0
	H = []
	pq.heappush(H, [0, 0])
	while H:
		(u2, u1) = pq.heappop(H)
		color[u1] = 1
		if d[u1] < u2:
			continue
		for (v1, v2) in M[u1]:
			if color[v1] == 1:
				continue
			if d[v1] > v2:
				d[v1] = v2
				pq.heappush(H, [d[v1], v1])
	return sum(d)
print(prim())


import heapq
(nv, ne) = map(int, input().split())
edges = [set() for _ in range(nv)]
while ne:
	(s, t, w) = map(int, input().split())
	edges[s].add((w, t))
	edges[t].add((w, s))
	ne -= 1
cost = 0
queue = list(edges[0])
heapq.heapify(queue)
visited = [False] * nv
visited[0] = True
while queue:
	(edge_cost, t) = heapq.heappop(queue)
	if visited[t]:
		continue
	visited[t] = True
	cost += edge_cost
	if all(visited):
		break
	for e in edges[t]:
		if not visited[e[1]]:
			heapq.heappush(queue, e)
print(cost)


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

	def root(x):
		if par[x] == x:
			return x
		par[x] = root(par[x])
		return par[x]

	def unite(x, y):
		x = root(x)
		y = root(y)
		if rank[x] < rank[y]:
			par[x] = y
		else:
			par[y] = x
			if rank[x] == rank[y]:
				rank[x] += 1
	(n, m) = LI()
	v = []
	for i in range(m):
		(a, b, c) = LI()
		v.append((c, a, b))
	v.sort()
	par = [i for i in range(n)]
	rank = [0] * n
	ans = 0
	for (c, x, y) in v:
		if root(x) != root(y):
			ans += c
			unite(x, y)
	print(ans)
	return
solve()


from collections import defaultdict
import sys
import heapq
sys.setrecursionlimit(10 ** 8)

def Find(x):
	global table
	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])
		return table[x]

def Union(x, y):
	x = Find(x)
	y = Find(y)
	if x == y:
		return
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x, y):
	if Find(x) == Find(y):
		return True
	else:
		return False
(N, E) = map(int, input().split())
table = [i for i in range(N)]
rank = [1 for i in range(N)]
q = []
heapq.heapify(q)
rout = defaultdict(set)
for i in range(E):
	(a, b, w) = list(map(int, input().split()))
	rout[a].add(b)
	rout[b].add(a)
	heapq.heappush(q, [w, a, b])
weight = 0
while q:
	(w, a, b) = heapq.heappop(q)
	if not Check(a, b):
		weight += w
		Union(a, b)
print(weight)


import sys
from operator import itemgetter

def solve():
	(n, m) = map(int, sys.stdin.readline().split())
	edges = [None] * m
	for i in range(m):
		(s, t, w) = map(int, sys.stdin.readline().split())
		edges[i] = (s, t, w)
	edges.sort(key=itemgetter(2), reverse=True)
	uf = UnionFind(n)
	ans = 0
	for i in range(n - 1):
		while edges:
			(s, t, w) = edges.pop()
			if not uf.same(s, t):
				uf.unite(s, t)
				break
		ans += w
	print(ans)

class UnionFind:

	def __init__(self, n):
		self.p = list(range(n))
		self.rank = [0] * n

	def find_root(self, x):
		if x != self.p[x]:
			self.p[x] = self.find_root(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def unite(self, x, y):
		u = self.find_root(x)
		v = self.find_root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
		else:
			self.p[v] = u
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
solve()


class DisjointSet:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n

	def make_set(self, x):
		self.par[x] = x
		self.rank[x] = 0

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.find(self.par[x])

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

class Edge:

	def __init__(self, source=0, target=0, cost=0):
		self.source = source
		self.target = target
		self.cost = cost

	def __lt__(self, e):
		return self.cost < e.cost

def kruskal(N, edges):
	total_cost = 0
	edges = sorted(edges)
	dset = DisjointSet(N)
	(source, target) = (0, 0)
	for i in range(E):
		e = edges[i]
		if not dset.same_check(e.source, e.target):
			total_cost += e.cost
			dset.unite(e.source, e.target)
	return total_cost
(V, E) = list(map(int, input().split(' ')))
edges = []
for i in range(E):
	(s, t, d) = list(map(int, input().split(' ')))
	edges.append(Edge(s, t, d))
print(kruskal(V, edges))


class unionfind:
	sz = 0
	par = []

	def __init__(self, n):
		self.sz = n
		for i in range(n):
			self.par.append(-1)

	def find(self, a):
		if self.par[a] < 0:
			return a
		self.par[a] = self.find(self.par[a])
		return self.par[a]

	def size(self, a):
		a = self.find(a)
		return -self.par[a]

	def same(self, a, b):
		return self.find(a) == self.find(b)

	def unite(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if self.same(a, b):
			return False
		if self.size(a) < self.size(b):
			(a, b) = (b, a)
		self.par[a] += self.par[b]
		self.par[b] = a
		return True
(n, m) = map(int, input().split())
g = []
for i in range(m):
	(s, t, w) = map(int, input().split())
	g.append([w, s, t])
g = sorted(g)
ans = 0
uni = unionfind(n)
for (c, i, j) in g:
	if uni.unite(i, j):
		ans += c
print(ans)


(V, E) = map(int, input().split())
PAR = list(range(V))

def root(x):
	if PAR[x] == x:
		return x
	else:
		PAR[x] = root(PAR[x])
		return PAR[x]

def same(x, y):
	return root(x) == root(y)

def unite(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	PAR[max(x, y)] = min(x, y)

class Edge:

	def __init__(self, u, v, cost):
		self.u = u
		self.v = v
		self.cost = cost
EDGES = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	EDGES.append(Edge(s, t, w))

def kruskal():
	edges = sorted(EDGES, key=lambda a: a.cost)
	res = 0
	for edge in edges:
		if not same(edge.u, edge.v):
			unite(edge.u, edge.v)
			res += edge.cost
	return res
print(kruskal())


import array
import collections
import heapq
AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
INF = 2 ** 31 - 1
NO_VERTEX = -1

def compute_mst_prim(max_v, adj_list):
	pred = collections.defaultdict(lambda : NO_VERTEX)
	key = collections.defaultdict(lambda : INF)
	key[0] = 0
	pq = [(key[v], v) for v in range(max_v)]
	heapq.heapify(pq)
	in_pq = array.array('B', (True for _ in range(max_v)))
	while pq:
		(_, u) = heapq.heappop(pq)
		in_pq[u] = False
		for (v, v_cost) in adj_list[u]:
			if in_pq[v]:
				weight = v_cost
				if weight < key[v]:
					pred[v] = u
					key[v] = weight
					heapq.heappush(pq, (weight, v))
					in_pq[v] = True
	return (pred, key)

def main():
	(max_v, max_e) = map(int, input().split())
	adjacency_list = collections.defaultdict(set)
	for _ in range(max_e):
		(s, t, w) = map(int, input().split())
		adjacency_list[s].add(AdjacentVertex(t, w))
		adjacency_list[t].add(AdjacentVertex(s, w))
	(_, key) = compute_mst_prim(max_v, adjacency_list)
	print(sum(key.values()))
main()


(v, e) = map(int, input().split())
data = []
for i in range(e):
	data.append(list(map(int, input().split())))
from collections import deque
q = deque(sorted(data, key=lambda x: x[2]))
parent = [i for i in range(v)]
rank = [0 for i in range(v)]

def find(x):
	if parent[x] == x:
		return x
	else:
		parent[x] = find(parent[x])
		return parent[x]

def judge(a, b):
	a_parent = find(a)
	b_parent = find(b)
	if a_parent == b_parent:
		return True
	else:
		return False

def merge(a, b):
	a_parent = find(a)
	b_parent = find(b)
	if a_parent == b_parent:
		return
	elif rank[a_parent] > rank[b_parent]:
		parent[b_parent] = a_parent
	elif rank[a_parent] < rank[b_parent]:
		parent[a_parent] = b_parent
	else:
		parent[a_parent] = b_parent
		rank[b_parent] += 1
ans = 0
while len(q) > 0:
	a = q.popleft()
	if not judge(a[0], a[1]):
		merge(a[0], a[1])
		ans += a[2]
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)
(V, E) = map(int, input().split(' '))
Edges = [tuple(map(int, input().split(' '))) for _ in range(E)]
Edges.sort(key=lambda x: x[2])
F = UnionFind(V)
cost = 0
for e in Edges:
	if F.same(e[0], e[1]):
		continue
	F.union(e[0], e[1])
	cost += e[2]
print(cost)


class DisjointSet:

	def __init__(self, size):
		self.rank = [0 for i in range(size)]
		self.p = [0 for i in range(size)]
		for i in range(size):
			self.makeSet(i)

	def makeSet(self, x):
		self.p[x] = x
		self.rank[x] = 0

	def same(self, x, y):
		return self.findSet(x) == self.findSet(y)

	def unite(self, x, y):
		self.link(self.findSet(x), self.findSet(y))

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def findSet(self, x):
		if x != self.p[x]:
			self.p[x] = self.findSet(self.p[x])
		return self.p[x]

def kruskal(V, e):
	e = sorted(e, key=lambda x: x[2])
	S = DisjointSet(V)
	K = []
	for (s, t, w) in e:
		if not S.same(s, t):
			S.unite(s, t)
			K.append((s, t, w))
	return K
(V, E) = map(int, input().split())
e = [tuple(map(int, input().split())) for i in range(E)]
K = kruskal(V, e)
ans = 0
for (s, t, w) in K:
	ans += w
print(ans)


from heapq import heappop, heappush
(v_num, e_num) = map(int, input().split())
pair_lst = [i for i in range(v_num)]
que = []
for _ in range(e_num):
	(s, t, w) = map(int, input().split())
	heappush(que, (w, s, t))

def find(x):
	if x == pair_lst[x]:
		return x
	else:
		tmp = find(pair_lst[x])
		pair_lst[x] = tmp
		return tmp
length_sum = 0
while que:
	(w, s, t) = heappop(que)
	root_s = find(s)
	root_t = find(t)
	if root_s != root_t:
		pair_lst[root_s] = root_t
		length_sum += w
print(length_sum)


class UnionFind:

	def __init__(self, num):
		self.parent = [i for i in range(num + 1)]

	def find(self, node):
		if self.parent[node] == node:
			return node
		self.parent[node] = self.find(self.parent[node])
		return self.parent[node]

	def union(self, node1, node2):
		node1 = self.find(node1)
		node2 = self.find(node2)
		if node1 == node2:
			return
		if self.parent[node1] > self.parent[node2]:
			(node1, node2) = (node2, node1)
		self.parent[node2] = node1
		return

	def same(self, node1, node2):
		return self.find(node1) == self.find(node2)

def kruskal(vertex_num, edges):
	ans = 0
	uf = UnionFind(vertex_num)
	edges.sort()
	for edge in edges:
		(cost, frm, to) = edge
		if uf.same(frm, to) is False:
			uf.union(frm, to)
			ans += cost
	return ans
(v, e) = map(int, input().split())
edges = []
for _ in range(e):
	(s, t, w) = map(int, input().split())
	edges.append([w, s, t])
print(kruskal(v, edges))


(v, e) = map(int, input().split())
s = sorted([list(map(int, input().split())) for i in range(e)], key=lambda x: x[2])
d = [i for i in range(v)]

def f(x):
	if x == d[x]:
		return x
	d[x] = f(d[x])
	return f(d[x])
a = 0
for (i, j, h) in s:
	(i, j) = (f(i), f(j))
	if i != j:
		d[i] = j
		a += h
print(a)


import heapq

def main():
	(n, m) = map(int, input().split())
	e = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		e[a].append([b, c])
		e[b].append([a, c])
	inf = 1000000007
	d = [inf] * n
	d[0] = 0
	visited = [False] * n
	pq = [[0, 0]]
	heapq.heapify(pq)
	while pq:
		(c, v) = heapq.heappop(pq)
		visited[v] = True
		for (u, nc) in e[v]:
			if not visited[u] and nc < d[u]:
				d[u] = nc
				heapq.heappush(pq, [nc, u])
	res = 0
	for i in range(n):
		res += d[i]
	print(res)
main()


import sys
import heapq as hp
(WHITE, GRAY, BLACK) = (0, 1, 2)

def generate_adj_table(v_table):
	for each in v_table:
		(v_from, v_to, edge_weight) = map(int, each)
		init_adj_table[v_from][v_to] = edge_weight
		init_adj_table[v_to][v_from] = edge_weight
	return init_adj_table

def prim_span_tree():
	distance[init_v] = 0
	parent[init_v] = -1
	path_heap = []
	hp.heappush(path_heap, (distance[init_v], init_v))
	while len(path_heap) >= 1:
		current_vertex = hp.heappop(path_heap)[1]
		color[current_vertex] = BLACK
		for (adj_vertex, adj_weight) in adj_table[current_vertex].items():
			if color[adj_vertex] is not BLACK:
				if adj_weight < distance[adj_vertex]:
					distance[adj_vertex] = adj_weight
					parent[adj_vertex] = current_vertex
					color[adj_vertex] = GRAY
					hp.heappush(path_heap, (adj_weight, adj_vertex))
	return distance
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
parent = [-1] * vertices
distance = [float('inf')] * vertices
color = [WHITE] * vertices
init_v = 0
init_adj_table = tuple((dict() for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
print(sum(prim_span_tree()))


import heapq
(num_V, num_E) = map(int, input().split())
E = [[] for _ in range(num_V)]
for _ in range(num_E):
	(ts, tt, tw) = map(int, input().split())
	E[ts].append([tt, tw])
	E[tt].append([ts, tw])
flg = [0] * num_V
ans = []
q = []
heapq.heappush(q, [0, 0])
while q:
	(cd, cp) = heapq.heappop(q)
	if flg[cp] == 0:
		flg[cp] = 1
		ans.append(cd)
	else:
		continue
	for (np, nd) in E[cp]:
		if flg[np] == 0:
			heapq.heappush(q, [nd, np])
print(sum(ans))


from collections import namedtuple

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.size = [1] * (n + 1)

	def is_same(self, a, b):
		return self.find(a) == self.find(b)

	def unite(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.par[b] = a
		self.size[a] += self.size[b]

	def size_of(self, a):
		return self.size[self.find(a)]

	def find(self, a):
		if a == self.par[a]:
			return a
		self.par[a] = self.find(self.par[a])
		return self.par[a]
Edge = namedtuple('Edge', 'w s t')
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges.append(Edge(w, s, t))
edges.sort()
u = UnionFind(V)
cost = 0
for (w, s, t) in edges:
	if u.is_same(s, t):
		continue
	u.unite(s, t)
	cost += w
print(cost)


(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges.append((w, s, t))
edges.sort()

def find(x):
	if par[x] < 0:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return False
	else:
		if par[x] > par[y]:
			(x, y) = (y, x)
		par[x] += par[y]
		par[y] = x
		return True

def same(x, y):
	return find(x) == find(y)

def size(x):
	return -par[find(x)]
par = [-1] * V
ans = 0
for e in edges:
	if same(e[1], e[2]):
		continue
	ans += e[0]
	unite(e[1], e[2])
print(ans)


import heapq

class Adjlist_weighted:

	def __init__(self, nodes, edges=None):
		self.nodes = nodes
		lis = [{} for i in range(nodes)]
		if edges is not None:
			for edge in edges:
				lis[edge[0]][edge[1]] = edge[2]
		self.edges = lis

	def add_edge(self, edge):
		self.edges[edge[0]][edge[1]] = edge[2]
		self.edges[edge[1]][edge[0]] = edge[2]
		return self

	def next_edges(self, x):
		return self.edges[x]

class Min_span_tree:

	def __init__(self, graph):
		min_span_tree = Adjlist_weighted(graph.nodes)
		searched_nodes = [False] * graph.nodes
		start = 0
		heap = [(0, start, start)]
		total_length = 0
		while heap:
			(cost, now, prev) = heapq.heappop(heap)
			if not searched_nodes[now]:
				searched_nodes[now] = True
				if (now, prev) != (start, start):
					min_span_tree.add_edge((prev, now, cost))
				cand = graph.next_edges(now)
				total_length += cost
				for next in cand:
					if not searched_nodes[next]:
						heapq.heappush(heap, (cand[next], next, now))
		self.min_span_tree = min_span_tree
		self.total_length = total_length
(V, E) = tuple(map(int, input().split(' ')))
graph = Adjlist_weighted(V)
for _ in range(E):
	graph.add_edge(tuple(map(int, input().split(' '))))
mst = Min_span_tree(graph)
print(mst.total_length)


class UnionFind:

	def __init__(self, v_count: int):
		self.par = [-1] * v_count
		for i in range(v_count):
			self.par[i] = i

	def root(self, x: int) -> int:
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def is_same(self, x: int, y: int) -> bool:
		return self.root(x) == self.root(y)

	def unite(self, x: int, y: int):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

def kruskal(v_count: int) -> int:
	global edges
	uf = UnionFind(v_count)
	cost = 0
	for (w, s, t) in sorted(edges):
		if not uf.is_same(s, t):
			uf.unite(s, t)
			cost += w
	return cost
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, w) = map(int, input().split())
	edges.append((w, s, t))
ans = kruskal(V)
print(ans)


class UnionFind:

	def __init__(self, size):
		self.parent = [i for i in range(size)]
		self.rank = [0] * size
		self.size = size

	def find(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.parent[x] = y
		else:
			self.parent[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

def kruskal() -> int:
	(total_cost, undetermined, uf) = (0, N, UnionFind(N))
	for (cost, v, u) in E:
		if not uf.is_same(v, u):
			uf.unite(v, u)
			total_cost += cost
			undetermined -= 1
		if not undetermined:
			break
	return total_cost

def main():
	global N, E
	(N, M, *E) = map(int, open(0).read().split())
	E = [(c, v, u) for (v, u, c) in zip(*[iter(E)] * 3)]
	E.sort()
	ans = kruskal()
	print(ans)
main()


from heapq import heappop, heappush

def kruskal(edges, v):
	nums = [i for i in range(v)]
	rank = [0 for i in range(v)]

	def find_top(x):
		if nums[x] != x:
			nums[x] = find_top(nums[x])
		return nums[x]

	def unite(x, y):
		x = find_top(x)
		y = find_top(y)
		if rank[x] > rank[y]:
			nums[y] = x
		else:
			nums[x] = y
			if rank[x] == rank[y]:
				rank[y] += 1

	def same(x, y):
		return find_top(x) == find_top(y)
	weight = 0
	while len(edges) > 0:
		(w, s, t) = heappop(edges)
		if not same(s, t):
			unite(s, t)
			weight += w
	return weight

def main():
	(v, e) = map(int, input().split())
	edges = []
	for _ in range(e):
		(s, t, w) = map(int, input().split())
		heappush(edges, (w, s, t))
	print(kruskal(edges, v))
main()