Given a graph which consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:  

The subgraph contains all the nodes present in the original graph.  
The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.  
It is also required that there is exactly one, exclusive path between any two nodes of the subgraph. 

One specific node $\mbox{S}$ is fixed as the starting point of finding the subgraph using Prim's Algorithm. 

Find the total weight or the sum of all edges in the subgraph.

Example 

$n=3$ 

$edges=[[1,2,2],[2,3,2],[1,3,3]]$ 

$start=1$   

Starting from node $\mbox{I}$, select the lower weight edge, i.e. $1\leftrightarrow2$, weight $2$.   

Choose between the remaining edges, $1\leftrightarrow3$, weight $3$, and $2\leftrightarrow3$, weight $2$.  

The lower weight edge is $2\leftrightarrow3$ weight $2$.   

All nodes are connected at a cost of $2+2=4$. The edge $1\leftrightarrow3$ is not included in the subgraph.   

Function Description

Complete the prims function in the editor below.  

prims has the following parameter(s):  

int n: the number of nodes in the graph  
int edges[m][3]: each element contains three integers, two nodes numbers that are connected and the weight of that edge  
int start: the number of the starting node  

Returns   

int: the minimum weight to connect all nodes in the graph

Input Format

The first line has two space-separated integers $n$ and $m$, the number of nodes and edges in the graph.  

Each of the next $m$ lines contains three space-separated integers $\mbox{u}$, $\boldsymbol{\nu}$ and $\boldsymbol{w}$, the end nodes of $\textit{edges}[i]$, and the edge's weight. 

The last line has an integer $\textit{start}$, the starting node.  

Constraints

$2\leq n\leq3000$ 

$1\leq m\leq(n*(n-1))/2$ 

$1\le u,v,start\le n$ 

$0\leq w\leq10^5$ 

There may be multiple edges between two nodes.

Sample Input 0
5 6
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
1

Sample Output 0
15

Explanation 0

The graph given in the test case is shown as :

The starting node is $\mbox{I}$ (in the given test case)

Applying the Prim's algorithm, edge choices available at first are :

$1\rightarrow2$ (WT. 3)  and $1\rightarrow3$ (WT. 4) , out of which $1\rightarrow2$ is chosen (smaller weight of edge).

Now the available choices are : 

$1\rightarrow3$ (WT. 4) , $2\rightarrow3$ (WT. 5) , $2\rightarrow5$ (WT. 2) and $2\rightarrow4$ (WT. 6) , out of which $2\rightarrow5$ is chosen by the algorithm. 

Following the same method of the algorithm, the next chosen edges , sequentially are :

$1\rightarrow3$ and $2\rightarrow4$.

Hence the overall sequence of edges picked up by Prim's are: 

$1\to2:2\to5:1\to3:2\to4$

and the total weight of the MST (minimum spanning tree) is : $3+2+4+6=15$

Difficulty: MEDIUM
Tags: Graph algorithms

Starter code:

Solutions:
from collections import defaultdict
import heapq

def prim(S, N, G):
	E = defaultdict(int)
	D = {}
	T = [0 for _ in range(N + 1)]
	H = [(0, S)]
	for n in range(1, N + 1):
		D[n] = float('inf')
	D[S] = 0
	while H:
		t = heapq.heappop(H)
		for h in G[t[1]]:
			if E[h[1]] == 0 and D[h[1]] > h[0]:
				D[h[1]] = h[0]
				if h in H:
					H.remove(h)
					heapq.heapify(H)
				heapq.heappush(H, (D[h[1]], h[1]))
				T[h[1]] = D[h[1]]
			E[t[1]] += 1
	return T

def main():
	(N, M) = [int(i) for i in input().split()]
	G = defaultdict(set)
	for _ in range(M):
		e = [int(i) for i in input().split()]
		G[e[0]].add((e[2], e[1]))
		G[e[1]].add((e[2], e[0]))
	S = int(input())
	print(sum(prim(S, N, G)))
main()


__author__ = 'Shivani'

class Edge:

	def __init__(self, w, v1, v2):
		self.v1 = v1
		self.v2 = v2
		self.w = w

def swap(l, i, j):
	temp = l[i]
	l[i] = l[j]
	l[j] = temp

def min_heapify(l, i):
	left = 2 * (i + 1) - 1
	right = 2 * (i + 1)
	x = i
	if left < len(l) and l[left].w < l[x].w:
		x = left
	if right < len(l) and l[right].w < l[x].w:
		x = right
	if x != i:
		swap(l, i, x)
		min_heapify(l, x)

def build_min_heap(l):
	i = len(l) // 2
	while i > -1:
		min_heapify(l, i)
		i -= 1

def extract_min(l):
	m = l[0]
	l[0] = l[len(l) - 1]
	del l[len(l) - 1]
	min_heapify(l, 0)
	return m

def decrease_key(l, i, key):
	l[i][1] = key
	p = i // 2
	while i > -1 and l[p].w > l[i].w:
		swap(l, p, i)

def insert(l, v, q):
	for e in l:
		if e.v1 in v and e.v2 in v:
			e.w = 100001
		else:
			q.append(e)

def prim(graph, s, n):
	q = []
	v = set([s])
	q.extend(graph[s])
	w = 0
	while len(v) < n:
		build_min_heap(q)
		j = extract_min(q)
		if j.v1 not in v or j.v2 not in v:
			if j.v1 not in v:
				w += j.w
				v.add(j.v1)
				insert(graph[j.v1], v, q)
			if j.v2 not in v:
				w += j.w
				v.add(j.v2)
				insert(graph[j.v2], v, q)
			j.w = 100001
	print(w)

def main():
	(n, e) = input().split()
	(n, e) = (int(n), int(e))
	graph = []
	for k in range(n):
		graph.append([])
	for j in range(e):
		(a, b, c) = input().split()
		(a, b, c) = (int(a), int(b), int(c))
		ed = Edge(c, a - 1, b - 1)
		graph[a - 1].append(ed)
		graph[b - 1].append(ed)
	s = int(input())
	prim(graph, s - 1, n)
main()


from heapq import heapify, heappush, heappop
(N, M) = input().split()
(N, M) = (int(N), int(M))
edges_for_node = [[] for _ in range(N)]
for _ in range(M):
	(x, y, r) = input().split()
	(x, y, r) = (int(x) - 1, int(y) - 1, int(r))
	edges_for_node[x].append((r, x, y))
	edges_for_node[y].append((r, y, x))
S = int(input()) - 1
candidate_edges = edges_for_node[S][:]
heapify(candidate_edges)
nodes_in_mst = set()
total_weight = 0
while candidate_edges:
	edge = heappop(candidate_edges)
	if not (edge[1] in nodes_in_mst and edge[2] in nodes_in_mst):
		total_weight += edge[0]
		if edge[1] not in nodes_in_mst:
			nodes_in_mst.add(edge[1])
			for e in edges_for_node[edge[1]]:
				heappush(candidate_edges, e)
		if edge[2] not in nodes_in_mst:
			nodes_in_mst.add(edge[2])
			for e in edges_for_node[edge[2]]:
				heappush(candidate_edges, e)
print(total_weight)


def Prims(graph, start, N):
	cost = 0
	X = set()
	X.add(start)
	while len(X) != N:
		crossing = set()
		for x in X:
			for y in graph[x]:
				if y not in X:
					crossing.add((x, y))
		edge = sorted(crossing, key=lambda e: graph[e[0]][e[1]])[0]
		cost += graph[edge[0]][edge[1]]
		X.add(edge[1])
	return cost
(N, M) = map(int, input().split())
graph = {}
for _ in range(0, M):
	(x, y, r) = map(int, input().split())
	if x in graph.keys() and y in graph[x].keys():
		if r > graph[x][y]:
			continue
	if x != y:
		if x in graph.keys():
			graph[x].update({y: r})
		else:
			graph[x] = {y: r}
		if y in graph.keys():
			graph[y].update({x: r})
		else:
			graph[y] = {x: r}
start = int(input())
print(Prims(graph, start, N))


from bisect import insort
(N, M) = [int(x) for x in input().split()]
marked = [False] * N
edges = []
for _ in range(N):
	edges.append([])
for _ in range(M):
	(x, y, r) = [int(x) for x in input().split()]
	edges[x - 1].append([r, y - 1])
	edges[y - 1].append([r, x - 1])
S = int(input()) - 1
q = [[0, S]]
s = 0
while q:
	(d, x) = q.pop(0)
	if marked[x]:
		continue
	marked[x] = True
	s += d
	for y in filter(lambda n: not marked[n[1]], edges[x]):
		insort(q, y)
print(s)


(N, M) = list(map(int, input().split(' ')))
adj = {}
D = {}
for v in range(1, N + 1):
	adj[v] = []
	D[v] = float('inf')
for m in range(M):
	(x, y, r) = list(map(int, input().split(' ')))
	adj[x].append((y, r))
	adj[y].append((x, r))
S = int(input())
D[S] = 0
Q = list(adj.keys())
Q.sort(key=lambda v: D[v])
L = 0
while len(Q) > 0:
	u = Q[0]
	d = D[u]
	L += d
	Q = Q[1:]
	for (v, r) in adj[u]:
		if r < D[v]:
			D[v] = r
	Q.sort(key=lambda v: D[v])
print(L)


INF = 9999999999
(N, M) = tuple(map(int, input().split()))
EDGE = []
EDGE_LENGTH = []

def init_edge(N):
	for i in range(N + 1):
		EDGE.append([])
		EDGE_LENGTH.append([])

def insert_edge(node1, node2, length):
	found = 0
	for i in range(len(EDGE[node1])):
		if EDGE[node1][i] == node2:
			if length < EDGE_LENGTH[node1][i]:
				EDGE_LENGTH[node1][i] = length
				found = 1
				break
	for i in range(len(EDGE[node2])):
		if EDGE[node2][i] == node1:
			if length < EDGE_LENGTH[node2][i]:
				EDGE_LENGTH[node2][i] = length
				found = 1
				break
	if found == 0:
		EDGE[node1].append(node2)
		EDGE[node2].append(node1)
		EDGE_LENGTH[node1].append(length)
		EDGE_LENGTH[node2].append(length)

def PRIM(start_node):
	Vertice_Not_Included = list(range(1, N + 1))
	Weight = dict()
	Parent = dict()
	for i in range(1, N + 1):
		if i == start_node:
			Weight[i] = 0
		else:
			Weight[i] = INF
	while len(Vertice_Not_Included) > 0:
		min_wt = INF
		curr = -1
		for node in Vertice_Not_Included:
			if Weight[node] < min_wt:
				min_wt = Weight[node]
				curr = node
		Vertice_Not_Included.remove(curr)
		for i in range(len(EDGE[curr])):
			adj = EDGE[curr][i]
			if adj in Vertice_Not_Included:
				if EDGE_LENGTH[curr][i] < Weight[adj]:
					Weight[adj] = EDGE_LENGTH[curr][i]
					Parent[adj] = curr
	Total_Weight = 0
	for key in Parent:
		index = 0
		for i in range(len(EDGE[key])):
			if EDGE[key][i] == Parent[key]:
				index = i
				break
		Total_Weight += EDGE_LENGTH[key][index]
	print(Total_Weight)
init_edge(N)
for _ in range(M):
	(node1, node2, length) = tuple(map(int, input().split()))
	insert_edge(node1, node2, length)
start_node = int(input())
PRIM(start_node)


class vertex:

	def __init__(self, x, y, w):
		self.x = x
		self.y = y
		self.w = w
		self.used = False
var = input().split()
(N, M) = (int(var[0]), int(var[1]))
V = {}
E = []
total_weight = 0
for i in range(0, M):
	var = input().split()
	(x, y, w) = (int(var[0]), int(var[1]), int(var[2]))
	E.append(vertex(x, y, w))
S = int(input())
E = sorted(E, key=lambda vertex: vertex.w)
for i in range(0, N):
	V[i + 1] = False
V[E[0].x] = True
complete = False
while complete == False:
	complete = True
	for e in E:
		if e.used == True:
			continue
		if (V[e.x] and V[e.y]) == True:
			complete = False
			e.used = True
			break
		elif V[e.x] == True and V[e.y] == False:
			complete = False
			V[e.y] = True
			total_weight += e.w
			e.used = True
			break
		elif V[e.y] == True and V[e.x] == False:
			complete = False
			V[e.x] = True
			total_weight += e.w
			e.used = True
			break
		elif V[e.x] or V[e.y] == False:
			complete = False
print(total_weight)


(n, m) = input().split()
(n, m) = (int(n), int(m))
edges = {x: [] for x in range(1, n + 1)}
max_weight = 0
for j in range(m):
	(n1, n2, w) = input().split()
	(n1, n2, w) = (int(n1), int(n2), int(w))
	if w > max_weight:
		max_weight = w
	edges[n1].append((n2, w, j))
	edges[n2].append((n1, w, j))
s = int(input())
weight = 0
tree = {s}
used = set()
while len(tree) < n:
	min_edge = max_weight
	min_node = None
	for node in tree:
		for edge in edges[node]:
			if edge[2] not in used and edge[0] not in tree:
				if edge[1] < min_edge:
					min_edge = edge[1]
					min_node = edge[0]
					used_edge = edge[2]
	tree.add(min_node)
	weight += min_edge
	used.add(used_edge)
print(weight)


import queue
G = []
C = []

def prim(s):
	res = 0
	Q = queue.PriorityQueue()
	Q.put((0, s))
	while not Q.empty():
		(c, v) = Q.get()
		if C[v] == 2:
			continue
		res += c
		C[v] = 2
		for (ct, u) in G[v]:
			if C[u] == 2:
				continue
			C[u] = 1
			Q.put((ct, u))
	return res
(n, m) = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
C = [0] * (n + 1)
for _ in range(m):
	(a, b, c) = list(map(int, input().split()))
	G[a].append((c, b))
	G[b].append((c, a))
s = int(input())
print(prim(s))


import heapq as hq

def prim(s, N, E):
	visited = set()
	key = {}
	for i in range(1, N + 1):
		key[i] = 1 << 29
	queue = [(key[i], i) for i in range(1, N + 1)]
	hq.heappush(queue, (0, s))
	key[s] = 0
	while queue:
		(d, u) = hq.heappop(queue)
		if u in visited:
			continue
		for t in E[u]:
			(v, r) = t
			if v not in visited and r < key[v]:
				key[v] = r
				hq.heappush(queue, (r, v))
		visited.add(u)
	ans = 0
	for k in key:
		ans += key[k]
	return ans
(N, M) = map(int, input().split(' '))
E = {}
for i in range(1, N + 1):
	E[i] = []
for i in range(0, M):
	(x, y, r) = map(int, input().split(' '))
	E[x].append((y, r))
	E[y].append((x, r))
s = int(input())
dist = prim(s, N, E)
print(dist)


from random import randint

def insert(queue, graph, node_1, node_2, first_check, last_check):
	if last_check == first_check:
		if graph[node_1][node_2] > graph[queue[0][first_check]][queue[1][last_check]]:
			queue[0].insert(first_check + 1, node_1)
			queue[1].insert(last_check + 1, node_2)
		else:
			queue[0].insert(first_check, node_1)
			queue[1].insert(last_check, node_2)
		return 0
	rand = randint(first_check, last_check)
	if graph[node_1][node_2] == graph[queue[0][rand]][queue[1][rand]]:
		queue[0].insert(rand, node_1)
		queue[1].insert(rand, node_2)
		return 0
	elif graph[node_1][node_2] < graph[queue[0][rand]][queue[1][rand]]:
		if rand != first_check:
			last_check = rand - 1
		else:
			last_check = first_check
		insert(queue, graph, node_1, node_2, first_check, last_check)
	else:
		if rand != last_check:
			first_check = rand + 1
		else:
			first_check = last_check
		insert(queue, graph, node_1, node_2, first_check, last_check)

def algo(graph, start, n):
	result = 0
	current = start
	queue_live = list(range(1, n + 1))
	current_list = [[], []]
	len_list = 0
	v = 1
	while v:
		for i in queue_live:
			if graph[current][i] != -1:
				if len_list == 0:
					current_list[0].append(current)
					current_list[1].append(i)
					len_list += 1
				else:
					insert(current_list, graph, current, i, 0, len_list - 1)
					len_list += 1
		try:
			queue_live.remove(current)
		except:
			pass
		try:
			current = current_list[1][0]
			a = current_list[0].pop(0)
			b = current_list[1].pop(0)
			len_list -= 1
			if a in queue_live or b in queue_live:
				result = result + graph[a][b]
			queue_live[0]
		except:
			v = 0
	print(result)

def main():
	nm = input()
	nm = nm.split()
	n = int(nm[0])
	m = int(nm[1])
	graph = [[-1] * (n + 1) for i in range(n + 1)]
	while m:
		xy = input().split()
		x = int(xy[0])
		y = int(xy[1])
		z = int(xy[2])
		if graph[x][y] == -1 or graph[y][x] == -1:
			graph[x][y] = z
			graph[y][x] = z
		elif graph[x][y] > z or graph[y][x] > z:
			graph[x][y] = z
			graph[y][x] = z
		m -= 1
	s = int(input())
	algo(graph, s, n)
main()


import sys

class Edge:

	def __init__(self, node_one, node_two, weight):
		self.n1 = node_one
		self.n2 = node_two
		self.w = weight

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

	def __repr__(self):
		return 'node A: {} weight: {} node B: {}'.format(self.n1, self.w, self.n2)
[N, M] = [int(X) for X in sys.stdin.readline().split()]
edges = list()
for _edge in range(M):
	[x, y, r] = [int(X) for X in sys.stdin.readline().split()]
	edges.append(Edge(x - 1, y - 1, r))
forest = list(range(N))
_S = int(sys.stdin.readline())
edges.sort(reverse=True)
result = 0
while edges:
	e = edges.pop()
	if forest[e.n1] != forest[e.n2]:
		(old, new) = sorted([forest[e.n1], forest[e.n2]])
		forest = [new if x == old else x for x in forest]
		result += e.w
print(result)


from heapq import heappush, heappop

def prim(G, S):
	visited = [0 for _ in range(len(G))]
	q = []
	MST = 0
	for e in G[S]:
		heappush(q, (e[1], e[0]))
		visited[S] = 1
	while q:
		(w, v) = heappop(q)
		if not visited[v]:
			visited[v] = 1
			for e in G[v]:
				if not visited[e[0]]:
					heappush(q, (e[1], e[0]))
			MST += w
	return MST
l = input().split()
(N, M) = (int(l[0]), int(l[1]))
G = [[] for _ in range(N + 1)]
for _ in range(M):
	(e1, e2, w) = map(int, input().split())
	G[e1].append((e2, w))
	G[e2].append((e1, w))
S = int(input())
print(prim(G, S))


import copy

class graph:

	def __init__(self, nodes, edges):
		self.nodes = {}
		self.edges = {}
		for i in range(1, nodes + 1):
			self.nodes[i] = set()
		self.edge_count = edges
		self.node_count = nodes

	def add_edge(self, node1, node2, length=6):
		if node1 not in self.nodes[node2]:
			self.nodes[node1].add(node2)
			self.nodes[node2].add(node1)
			self.edges[node1, node2] = length
			self.edges[node2, node1] = length
		else:
			length = min(length, self.edges[node1, node2])
			self.edges[node1, node2] = length
			self.edges[node2, node1] = length

	def __str__(self):
		print(self.edges)
		return str(self.nodes)

	def mi(self, node, visited):
		data = []
		for x in self.nodes[node]:
			if x not in visited:
				data.append((x, self.edges[node, x]))
		if data != []:
			return min(data, key=lambda x: x[1])
		else:
			return (10000000.0, 10000000.0)

	def prim(self, start):
		visited = {start}
		s = []
		for _ in range(self.node_count - 1):
			node_select = []
			for i in visited:
				node_select.append(self.mi(i, visited))
			node_select = min(node_select, key=lambda x: x[1])
			visited.add(node_select[0])
			s.append(node_select)
		return sum([x[1] for x in s])
(nodes, edges) = map(int, input().split())
g = graph(nodes, edges)
for _ in range(edges):
	(node1, node2, length) = map(int, input().split())
	g.add_edge(node1, node2, length)
start = int(input())
print(g.prim(start))


from collections import defaultdict

class Graph:

	def __init__(self):
		self.neighbors = defaultdict(set)
		self.vertices = list()

	def add_edge(self, start, end, distance):
		self.neighbors[start].add((end, distance))
		self.neighbors[end].add((start, distance))

def prim(graph, start):
	infinity = object()
	tree = set([start])
	total = 0
	while len(tree) != len(graph.vertices):
		edge = None
		minimum = infinity
		for u in tree:
			for (v, w) in graph.neighbors[u]:
				if v in tree:
					continue
				if minimum is infinity or minimum > w:
					minimum = w
					edge = (u, v)
		if minimum is infinity:
			raise Exception
		total += minimum
		tree.add(edge[1])
		graph.neighbors[edge[0]].remove((edge[1], minimum))
		graph.neighbors[edge[1]].remove((edge[0], minimum))
	return total
graph = Graph()
(N, M) = map(int, input().split())
for name in range(1, N + 1):
	graph.vertices.append(name)
for _ in range(M):
	(start, end, distance) = map(int, input().split())
	graph.add_edge(start, end, distance)
S = int(input())
print(prim(graph, S))


class Graph(object):

	def __init__(self, size):
		self.size = size
		self.components = [{e} for e in range(1, size + 1)]
		super(Graph, self).__init__()

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

	def add_edge(self, edge):
		(u, v) = edge
		for cp in self.components:
			if u in cp:
				c1 = self.components.index(cp)
			if v in cp:
				c2 = self.components.index(cp)
		if c1 != c2:
			self.components[c1] = self.components[c1].union(self.components[c2])
			del self.components[c2]

	def induces_cycle(self, edge):
		(u, v) = edge
		for cp in self.components:
			if u in cp:
				c1 = self.components.index(cp)
			if v in cp:
				c2 = self.components.index(cp)
		if c1 == c2:
			return True
		return False
(N, M) = (int(s) for s in input().split(' '))
edges = []
for _ in range(M):
	(u, v, w) = (int(s) for s in input().split(' '))
	edges.append([(u, v), w])
input()
g = Graph(N)
edges = sorted(edges, key=lambda e: e[1])
k = 0
ct = 0
while len(g) > 1:
	if not g.induces_cycle(edges[k][0]):
		g.add_edge(edges[k][0])
		ct += edges[k][1]
	k += 1
print(ct)


import sys

def min_distance(mstSet, key):
	Min = sys.maxsize
	Mindex = -1
	for i in range(N + 1):
		if mstSet[i] == False and key[i] <= Min:
			Min = key[i]
			Mindex = i
	return Mindex

def primsMST(g, source):
	mstSet = [False for _ in range(N + 1)]
	key = [sys.maxsize for _ in range(N + 1)]
	key[source] = 0
	for _ in range(N):
		u = min_distance(mstSet, key)
		mstSet[u] = True
		adj = g[u]
		for i in range(len(adj)):
			if mstSet[adj[i][0]] == False and adj[i][1] < key[adj[i][0]]:
				key[adj[i][0]] = adj[i][1]
	print(sum((k for k in key if k != sys.maxsize)))
(N, M) = map(int, input().split())
g = {}
for i in range(1, N + 1):
	g[i] = []
for _ in range(M):
	(h, t, r) = map(int, input().split())
	g[h].append([t, r])
	g[t].append([h, r])
source = int(input())
primsMST(g, source)


graph = {}

def add_edge(x, y, d):
	graph.setdefault(x, []).append(y)
	graph.setdefault(y, []).append(x)
	graph[x, y] = d
	graph[y, x] = d
import heapq

def prim(s, n):
	heap = []
	heap.append((0, s))
	visited = {}
	w = 0
	while heap and len(visited) < n:
		(distance, current) = heapq.heappop(heap)
		if current not in visited:
			visited[current] = 1
			w += distance
			for ne in graph[current]:
				heapq.heappush(heap, (graph[current, ne], ne))
	if len(visited) == n:
		return w
	return -1
import sys
state = counter = n = m = 0
for line in sys.stdin:
	if state == 0:
		(n, m) = [int(e) for e in line.strip().split(' ')]
		state = 1
	elif state == 1:
		add_edge(*[int(e) for e in line.strip().split(' ')])
		counter += 1
		if counter == m:
			state = 2
	elif state == 2:
		s = int(line.strip())
		print(prim(s, n))


(n, m) = list(map(int, input().split(' ')))
edges = [[] for x in range(n)]
nodes = [x for x in range(n)]
for x in range(m):
	(a, b, r) = list(map(int, input().split(' ')))
	edges[a - 1].append([b - 1, r])
	edges[b - 1].append([a - 1, r])
s = int(input()) - 1
sub_nodes_enum = [s]
sub_nodes_bool = [False for x in range(n)]
sub_nodes_bool[s] = True
weight = 0
while True:
	min_volume = -1
	min_index = -1
	for x in sub_nodes_enum:
		for y in edges[x]:
			if not sub_nodes_bool[y[0]]:
				if y[1] < min_volume or min_volume == -1:
					min_volume = y[1]
					min_index = y[0]
	if min_volume != -1:
		sub_nodes_enum.append(min_index)
		sub_nodes_bool[min_index] = True
		weight += min_volume
	if len(sub_nodes_enum) == n:
		break
print(weight)


from collections import defaultdict
import heapq
(v, e) = map(int, input().split(' '))
g = defaultdict(dict)
for i in range(e):
	(u, v, w) = map(int, input().split(' '))
	g[u][v] = w
	g[v][u] = w
s = int(input())
mst = []
q = []
visited = set([s])
for v in g[s]:
	heapq.heappush(q, (g[s][v], s, v))
while q:
	e = heapq.heappop(q)
	u = e[2]
	if u in visited:
		continue
	mst.append(e)
	visited.add(u)
	for v in g[u]:
		if v not in visited:
			heapq.heappush(q, (g[u][v], u, v))
print(sum((e[0] for e in mst)))


from heapq import heappush, heappop

class Edge:
	__slots__ = ('origin', 'dest', 'weight')

	def __init__(self, origin, dest, weight):
		self.origin = origin
		self.dest = dest
		self.weight = weight

	def __repr__(self):
		return '{{{} {}}}'.format(self.origin, self.dest)

	def opposite(self, v):
		return self.dest if v == self.origin else self.origin

class Graph:

	def __init__(self, vertices):
		self.vertices = [[] for i in range(vertices)]

	def insert_edge(self, u, v, w):
		e = Edge(u, v, w)
		self.vertices[u].append(e)
		self.vertices[v].append(e)

	def incident_edges(self, v):
		for edge in self.vertices[v]:
			yield edge
(N, M) = map(int, input().split())
g = Graph(5000)
for _ in range(M):
	(x, y, r) = map(int, input().split())
	g.insert_edge(x, y, r)
start = int(input())
R = 0
D = [float('inf') for i in range(5000)]
heap = [(0, start)]
seen = [False] * 5000
while heap:
	(w, u) = heappop(heap)
	if not seen[u]:
		R += w
		seen[u] = True
		for e in g.incident_edges(u):
			v = e.opposite(u)
			if e.weight < D[v]:
				D[v] = e.weight
				heappush(heap, (e.weight, v))
print(R)


(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(x, y, r) = map(int, input().split())
	edges.append([x, y, r])
S = int(input())

class MinimumPriorityQueue:
	A = []

	def __init__(self, source, get_priority_func, set_priority_func):
		self.get_priority_func = get_priority_func
		self.set_priority_func = set_priority_func
		self.A = [None]
		self.A.extend(source)
		for i in range(1, len(self.A)):
			self.A[i].min_heap_index = i
		for i in range(len(self.A) // 2, 0, -1):
			self.min_heapify(i)

	def __bool__(self):
		return len(self.A) > 1

	def heap_size(self):
		return len(self.A) - 1

	def priority(self, i):
		return self.get_priority_func(self.A[i])

	def set_priority(self, i, new_prioriy):
		self.set_priority_func(self.A[i], new_prioriy)

	def swap_items(self, i, j):
		(self.A[i].min_heap_index, self.A[j].min_heap_index) = (j, i)
		(self.A[i], self.A[j]) = (self.A[j], self.A[i])

	def heap_extract_min(self):
		if self.heap_size() < 1:
			raise RuntimeError('heap underflow')
		minimum = self.A[1]
		self.A[1] = self.A[-1]
		self.A[1].min_heap_index = 1
		del self.A[-1]
		self.min_heapify(1)
		return minimum

	def min_heapify(self, i):
		l = i * 2
		r = i * 2 + 1
		smallest = i
		if l <= self.heap_size() and self.priority(l) < self.priority(i):
			smallest = l
		if r <= self.heap_size() and self.priority(r) < self.priority(smallest):
			smallest = r
		if smallest != i:
			self.swap_items(i, smallest)
			self.min_heapify(smallest)

	def heap_decrease_value(self, node, new_value):
		i = node.min_heap_index
		if new_value > self.priority(i):
			raise RuntimeError('new value larger than current value')
		self.set_priority(i, new_value)
		while i > 1 and self.priority(i // 2) > self.priority(i):
			self.swap_items(i, i // 2)
			i //= 2

class Vertex:

	def __init__(self, label):
		self.label = label
		self.edges = []
		self.parent = None
		self.priority = None
		self.in_queue = True
		self.min_heap_index = 0

def set_new_priority(v, p):
	v.priority = p
vertices = {}
vertex_names = {e[0] for e in edges}.union({e[1] for e in edges})
for vertex_name in vertex_names:
	vertex = Vertex(vertex_name)
	vertex.priority = 1000000000
	vertices[vertex_name] = vertex
for edge in edges:
	vertices[edge[0]].edges.append([vertices[edge[1]], edge[2]])
	vertices[edge[1]].edges.append([vertices[edge[0]], edge[2]])
vertices[S].priority = 0
Q = MinimumPriorityQueue(vertices.values(), lambda n: n.priority, set_new_priority)
A = []
while Q:
	u = Q.heap_extract_min()
	u.in_queue = False
	if u.parent is not None:
		A.append([u.parent, u, u.priority])
	for (v, w) in u.edges:
		if v.in_queue and w < v.priority:
			v.parent = u
			Q.heap_decrease_value(v, w)
sum = 0
for a in A:
	sum += a[2]
print(sum)


def prims(n, edges, s):
	q = [int(x) for x in range(1, n + 1) if x != s]
	vs = [s]
	f = []
	cost = 0
	while q:
		mini = 100001
		minidex = 0
		for (i, (w, u, v)) in enumerate(edges):
			if w < mini and (u not in vs) != (v not in vs):
				minidex = i
				mini = w
		(w, u, v) = edges[minidex]
		if u not in vs:
			q.remove(u)
			vs.append(u)
			f.append((w, u, v))
			edges.remove((w, u, v))
			cost += w
		elif v not in vs:
			q.remove(v)
			vs.append(v)
			f.append((w, u, v))
			edges.remove((w, u, v))
			cost += w
	return cost
[n, m] = [int(x) for x in input().strip().split()]
edges = []
for i in range(m):
	(u, v, w) = [int(x) for x in input().strip().split()]
	edges.append((w, u, v))
s = int(input())
print(prims(n, edges, s))


class Graph:

	def __init__(self, N, M):
		self.N = N
		self.M = M
		self.edges = {key: list() for key in range(1, N + 1)}
		for _ in range(M):
			(u, v, w) = [int(x) for x in input().split()]
			self.edges[u].append((v, w))
			self.edges[v].append((u, w))

	def prims(self, s):
		tree = set()
		tree_weight = 0
		distance = {}
		distance[s] = 0
		v = s
		while v not in tree:
			tree.add(v)
			tree_weight += distance[v]
			for (node, weight) in self.edges[v]:
				if node in tree:
					continue
				if node not in distance or distance[node] > weight:
					distance[node] = weight
			min_dist = -1
			for (node, dist) in distance.items():
				if node in tree:
					continue
				if min_dist < 0 or dist < min_dist:
					min_dist = dist
					v = node
		return tree_weight
(N, M) = [int(x) for x in input().split()]
g = Graph(N, M)
S = int(input())
print(g.prims(S))


from heapq import heappush, heappop, heapify
graph = []

def prims(source, n):
	total = 0
	visited = n * [False]
	edges = []
	visited[source] = True
	for i in range(n):
		temp = graph[source][i]
		if i != source and temp < 10 ** 6:
			edges.append((temp, source, i))
	for _ in range(n - 1):
		heapify(edges)
		while edges:
			edge = heappop(edges)
			if visited[edge[2]] == False:
				break
		source = edge[2]
		visited[source] = True
		for i in range(n):
			if visited[i] == False:
				temp = graph[source][i]
				if temp < 10 ** 6:
					edges.append((temp, source, i))
		total += edge[0]
	print(total)
(n, m) = map(int, input().split())
graph = [n * [10 ** 6] for _ in range(n)]
for _ in range(m):
	(a, b, l) = map(int, input().split())
	a -= 1
	b -= 1
	if graph[a][b] > l:
		graph[a][b] = l
		graph[b][a] = l
source = int(input()) - 1
prims(source, n)


def spaning_tree_cost(graph, vertex_cnt, start):
	vertexes = [False] * vertex_cnt
	vertex_costs = [100001] * vertex_cnt
	vertex_costs[start] = 0
	while True:
		chosen = None
		for i in range(vertex_cnt):
			if not vertexes[i] and (chosen == None or vertex_costs[chosen] > vertex_costs[i]):
				chosen = i
		if chosen == None:
			break
		vertexes[chosen] = True
		node = graph[chosen]
		while node != None:
			if not vertexes[node[0]] and node[1] < vertex_costs[node[0]]:
				vertex_costs[node[0]] = node[1]
			node = node[2]
	return sum(vertex_costs)
(vertex_cnt, edge_cnt) = [int(i) for i in input().split()]
graph = [None] * vertex_cnt
for i in range(edge_cnt):
	(node1, node2, cost) = [int(i) for i in input().split()]
	graph[node1 - 1] = (node2 - 1, cost, graph[node1 - 1])
	graph[node2 - 1] = (node1 - 1, cost, graph[node2 - 1])
start = int(input()) - 1
print(spaning_tree_cost(graph, vertex_cnt, start))


(N, M) = [int(i) for i in input().split()]
neighbors = [[] for i in range(N + 1)]
for i in range(M):
	(v1, v2, d) = [int(i) for i in input().split()]
	neighbors[v1].append((v2, d))
	neighbors[v2].append((v1, d))
S = int(input())
mark = set([])
Q = [S]
dist = {S: 0}
while len(Q) > 0:
	u = min(Q, key=lambda x: dist[x])
	Q.remove(u)
	mark.add(u)
	for neighbor_elem in neighbors[u]:
		v = neighbor_elem[0]
		d = neighbor_elem[1]
		if v in mark:
			continue
		if v not in dist:
			dist[v] = d
			Q.append(v)
		else:
			dist[v] = min(dist[v], d)
print(sum(dist.values()))


import operator
(n, m) = map(int, input().split())
edges = {}
for __ in range(0, m):
	(x, y, r) = map(int, input().split())
	x -= 1
	y -= 1
	(x, y) = (min(x, y), max(x, y))
	if (x, y) in edges:
		edges[x, y] = min(edges[x, y], r)
	else:
		edges[x, y] = r
s = int(input()) - 1
trees = []
sorted_edges = sorted(edges.items(), key=operator.itemgetter(1), reverse=True)
s = 0
while len(sorted_edges) > 0:
	((x, y), r) = sorted_edges.pop()
	ok = True
	xi = None
	yi = None
	for k in range(0, len(trees)):
		if x in trees[k] and y in trees[k]:
			ok = False
			break
		elif x in trees[k]:
			trees[k].add(y)
			xi = k
		elif y in trees[k]:
			trees[k].add(x)
			yi = k
	if ok:
		s += r
		if xi != None and yi != None:
			trees[xi] |= trees[yi]
			trees.pop(yi)
		elif xi != None:
			trees[xi].add(y)
		elif yi != None:
			trees[yi].add(x)
		else:
			trees.append({x, y})
print(s)


import heapq

class Graph:

	def __init__(self, vertexCount):
		self.vertexCount = vertexCount
		self.nodes = []
		for v in range(vertexCount):
			self.nodes.append(node(v))

	def addEdge(self, x, y, w):
		self.nodes[y].addEdge(x, w)
		self.nodes[x].addEdge(y, w)

	def Prims(self, start):
		self.nodes[start].key = 0
		queue = [v for v in self.nodes]
		heapq.heapify(queue)
		while len(queue):
			u = heapq.heappop(queue)
			self.nodes[u.nodeNumber].visited = 1
			for v in u.adjacentList.keys():
				if self.nodes[v].visited == 0 and u.adjacentList[v] < self.nodes[v].key:
					self.nodes[v].key = u.adjacentList[v]
					self.nodes[v].pi = v
			heapq.heapify(queue)
		MSTWeight = 0
		for node in self.nodes:
			MSTWeight = MSTWeight + node.key
		return MSTWeight

class node:

	def __init__(self, nodeNumber):
		self.nodeNumber = nodeNumber
		self.key = float('inf')
		self.pi = -1
		self.visited = 0
		self.adjacentList = {}

	def addEdge(self, y, w):
		try:
			if self.adjacentList[y] > w:
				self.adjacentList[y] = w
		except KeyError:
			self.adjacentList[y] = w

	def __lt__(self, other):
		return self.key < other.key
[N, M] = list(map(int, input().split()))
graph = Graph(N)
for m in range(M):
	[x, y, w] = list(map(int, input().split()))
	graph.addEdge(x - 1, y - 1, w)
minWeight = graph.Prims(int(input()) - 1)
print(minWeight)


import heapq

class Graph:

	def __init__(self, vertexCount):
		self.vertexCount = vertexCount
		self.nodes = []
		for v in range(vertexCount):
			self.nodes.append(node(v))

	def addEdge(self, x, y, w):
		self.nodes[y].addEdge(x, w)
		self.nodes[x].addEdge(y, w)

	def Prims(self, start):
		self.nodes[start].key = 0
		queue = [v for v in self.nodes]
		heapq.heapify(queue)
		while len(queue):
			u = heapq.heappop(queue)
			self.nodes[u.nodeNumber].visited = 1
			for v in u.adjacentList.keys():
				if self.nodes[v].visited == 0 and u.adjacentList[v] < self.nodes[v].key:
					self.nodes[v].key = u.adjacentList[v]
					self.nodes[v].pi = v
			heapq.heapify(queue)
		MSTWeight = 0
		for node in self.nodes:
			MSTWeight = MSTWeight + node.key
		return MSTWeight

class node:

	def __init__(self, nodeNumber):
		self.nodeNumber = nodeNumber
		self.key = float('inf')
		self.pi = -1
		self.visited = 0
		self.adjacentList = {}

	def addEdge(self, y, w):
		try:
			if self.adjacentList[y] > w:
				self.adjacentList[y] = w
		except KeyError:
			self.adjacentList[y] = w

	def __lt__(self, other):
		return self.key < other.key
[N, M] = list(map(int, input().split()))
graph = Graph(N)
for m in range(M):
	[x, y, w] = list(map(int, input().split()))
	graph.addEdge(x - 1, y - 1, w)
minWeight = graph.Prims(int(input()) - 1)
print(minWeight)


(N, M) = map(int, input().split())
g = [[-1 if x != y else 0 for x in range(N + 1)] for y in range(N + 1)]
for m in range(M):
	(x, y, r) = map(int, input().split())
	g[x][y] = r if g[x][y] == -1 else min(g[x][y], r)
	g[y][x] = r if g[x][y] == -1 else min(g[x][y], r)
s = int(input())
(q, w) = ([], [])
flag = [0 for x in range(N + 1)]
flag[s] = 1
sw = 0
while 1:
	q.extend(filter(None, [x if g[s][x] != -1 and flag[x] == 0 else [] for x in range(N + 1)]))
	w.extend(filter(None, [g[s][x] + 1 if g[s][x] != -1 and flag[x] == 0 else [] for x in range(N + 1)]))
	while q.count(s) > 0:
		idx = q.index(s)
		q.pop(idx)
		w.pop(idx)
	if not q:
		break
	sw += min(w) - 1
	s = q[w.index(min(w))]
	flag[s] = 1
print(sw)


def weight(nodes, edges, start_point):
	sub_nodes = {start_point}
	w = 0
	while sub_nodes != nodes:
		min_weight = 10 ** 10
		extra_point = start_point
		for edge in edges:
			if edge[0] in sub_nodes and edge[1] not in sub_nodes and (edge[2] < min_weight):
				extra_point = edge[1]
				min_weight = edge[2]
			elif edge[0] not in sub_nodes and edge[1] in sub_nodes and (edge[2] < min_weight):
				extra_point = edge[0]
				min_weight = edge[2]
			else:
				pass
		w += min_weight
		sub_nodes.add(extra_point)
	return w
(node_number, edge_number) = tuple((int(i) for i in input().strip().split()))
nodes = set(range(1, node_number + 1))
edges = set()
for i in range(edge_number):
	edges.add(tuple((int(i) for i in input().strip().split())))
start_point = int(input().strip())
print(weight(nodes, edges, start_point))


import heapq

class Heap:
	REMOVED = None

	def __init__(self, initial=[], key=lambda x: x):
		self.key = key
		self.entry_count = 0
		self._data = []
		self.entry_finder = {}
		for item in initial:
			self.push(item)

	def push(self, item):
		if item in self.entry_finder:
			self.remove_item(item)
		entry = [self.key(item), self.entry_count, item]
		self.entry_finder[item] = entry
		heapq.heappush(self._data, entry)
		self.entry_count += 1

	def remove_item(self, item):
		entry = self.entry_finder.pop(item)
		entry[-1] = self.REMOVED

	def pop(self):
		while self._data:
			(item_key, count, item) = heapq.heappop(self._data)
			if item is not self.REMOVED:
				del self.entry_finder[item]
				return item
		raise KeyError('pop from empty heap')

class Node:

	def __init__(self):
		self.value = float('inf')
		self.neighbors = set()

def read_nodes():
	(n, m) = [int(value) for value in input().split(' ')]
	unpicked_nodes = [Node() for _ in range(n)]
	for _ in range(m):
		(x, y, r) = [int(value) for value in input().split(' ')]
		unpicked_nodes[x - 1].neighbors.add((unpicked_nodes[y - 1], r))
		unpicked_nodes[y - 1].neighbors.add((unpicked_nodes[x - 1], r))
	return unpicked_nodes

def get_mst(unpicked_nodes):
	if len(unpicked_nodes) == 0:
		return 0
	node = unpicked_nodes[0]
	unpicked_nodes = set(unpicked_nodes)
	node.value = 0
	keyed_nodes = Heap(initial=[node], key=lambda node: node.value)
	cost = 0
	while True:
		try:
			node = keyed_nodes.pop()
		except KeyError:
			break
		unpicked_nodes.remove(node)
		cost += node.value
		for (neighbor, weight) in node.neighbors:
			if neighbor in unpicked_nodes and weight < neighbor.value:
				neighbor.value = weight
				keyed_nodes.push(neighbor)
	return cost
nodes = read_nodes()
print(get_mst(nodes))


class UndirectedGraphLength(object):

	def __init__(self, num_nodes):
		self.nodes = {node: {} for node in range(1, num_nodes + 1)}

	def __str__(self):
		return self.nodes

	def add_edge(self, edge, length):
		node1 = edge[0]
		node2 = edge[1]
		self.nodes[node2][node1] = length
		self.nodes[node1][node2] = length

	def find_minimum_spanning(self, origin):
		maxim = 10 ** 5
		found_nodes = {origin: 0}
		total_distance = 0
		node_to_check = self.nodes[origin]
		while len(found_nodes) < len(self.nodes):
			smallest = None
			smallest_length = maxim
			for (end, length) in node_to_check.items():
				if end not in found_nodes and length < smallest_length:
					smallest = end
					smallest_length = length
			total_distance += smallest_length
			found_nodes[smallest] = smallest_length
			for (new_node, new_length) in self.nodes.get(smallest, {}).items():
				if new_length < node_to_check.get(new_node, maxim):
					node_to_check[new_node] = new_length
		return total_distance

def main():
	(num_nodes, num_edges) = [int(i) for i in input().split(' ')]
	graph = UndirectedGraphLength(num_nodes)
	for i in range(num_edges):
		(start, end, length) = [int(i) for i in input().split(' ')]
		graph.add_edge([start, end], length)
	origin = int(input())
	minimum_spanning_length = graph.find_minimum_spanning(origin)
	print(minimum_spanning_length)
main()


from collections import namedtuple
import heapq
Edge = namedtuple('Edge', ['cost', 'dest'])

def solve(n, m, edge_list, s):
	next_edge_queue = []
	included_nodes = set([s])
	total_cost = 0
	for edge in edge_list[s]:
		heapq.heappush(next_edge_queue, edge)
	while len(included_nodes) < n:
		selected_node = None
		while selected_node == None:
			selected_node = heapq.heappop(next_edge_queue)
			if selected_node.dest in included_nodes:
				selected_node = None
			else:
				included_nodes.add(selected_node.dest)
				total_cost += selected_node.cost
		for dest in edge_list[selected_node.dest]:
			heapq.heappush(next_edge_queue, dest)
	return total_cost

def main():
	(N, M) = (int(v) for v in input().split())
	ES = [set() for _ in range(N + 1)]
	for _ in range(M):
		(v1, v2, cost) = (int(v) for v in input().split())
		ES[v1].add(Edge(cost, v2))
		ES[v2].add(Edge(cost, v1))
	S = int(input())
	print(solve(N, M, ES, S))
main()


import heapq
(n, m) = map(int, input().split())
a = [[] for i in range(n + 1)]
ans = 0
al = [0 for i in range(n + 1)]
q = []
heapq.heapify(q)
for i in range(m):
	(x, y, r) = map(int, input().split())
	a[x].append((r, y))
	a[y].append((r, x))
s = int(input())
heapq.heappush(q, (0, s))
while q:
	v = heapq.heappop(q)
	if not al[v[1]]:
		ans = ans + v[0]
		al[v[1]] = 1
	for i in a[v[1]]:
		if not al[i[1]]:
			heapq.heappush(q, i)
print(ans)


import queue

class MyEdge:

	def __init__(self, a, b, edgeLength):
		(self.x, self.y) = (a, b)
		self.length = edgeLength
		self.inMST = False

	def elligible(self):
		return self.x.inMST != self.y.inMST

class MyNode:

	def __init__(self):
		self.edges = []
		self.inMST = False
(numNodes, numEdges) = [int(x) for x in input().split()]
graph = []
for _ in range(numNodes):
	graph.append(MyNode())
for _ in range(numEdges):
	(a, b, length) = [int(x) for x in input().split()]
	(a, b) = (a - 1, b - 1)
	edge = MyEdge(graph[a], graph[b], length)
	graph[a].edges.append(edge)
	graph[b].edges.append(edge)
s = int(input()) - 1
MST = [graph[s]]
graph[s].inMST = True
totalWeight = 0
for _ in range(numNodes - 1):
	minEdge = None
	for node in MST:
		for edge in node.edges:
			if edge.elligible() and (minEdge is None or minEdge.length > edge.length):
				minEdge = edge
	totalWeight += minEdge.length
	if minEdge.x.inMST:
		MST.append(minEdge.y)
		minEdge.y.inMST = True
	else:
		MST.append(minEdge.x)
		minEdge.x.inMST = True
	minEdge.inMST = True
print(totalWeight)


class Node:

	def __init__(self, label):
		self.label = label
		self.adjacent_nodes = set()
		self.children = set()

def build_graph(nodes, edges):
	graph = dict()
	for label in range(1, nodes + 1):
		graph[label] = Node(label)
	for _ in range(edges):
		(first, second, distance) = tuple((int(number) for number in input().split()))
		graph[first].adjacent_nodes.add((graph[second], distance))
		graph[second].adjacent_nodes.add((graph[first], distance))
	return graph

def find_the_closest_node(node, tree):
	min_distance = float('inf')
	the_closest_node = None
	for (adjacent_node, distance) in node.adjacent_nodes:
		if adjacent_node not in tree and distance <= min_distance:
			min_distance = distance
			the_closest_node = adjacent_node
	return (the_closest_node, min_distance)

def build_tree(tree=None, start_node=None):
	if not tree:
		tree = {start_node}
	min_distance = float('inf')
	the_closest_node = None
	father_node = None
	for node in tree:
		(canidate_closest_node, candidate_distance) = find_the_closest_node(node, tree)
		if candidate_distance <= min_distance:
			min_distance = candidate_distance
			the_closest_node = canidate_closest_node
			father_node = node
	if the_closest_node:
		father_node.children.add((the_closest_node, min_distance))
		tree.add(the_closest_node)
	return (tree, the_closest_node)

def calculate_weight(start_node):
	total_distance = 0
	for (child_node, distance) in start_node.children:
		total_distance += distance + calculate_weight(child_node)
	return total_distance
(nodes, edges) = tuple((int(number) for number in input().split()))
graph = build_graph(nodes, edges)
start_node = graph[int(input())]
(tree, the_closest_node) = build_tree(start_node=start_node)
while the_closest_node:
	(tree, the_closest_node) = build_tree(tree)
print(calculate_weight(start_node))


import heapq

def Pmst(G, N, S):
	dist = [float('inf') for i in range(N)]
	visited = [False for i in range(N)]
	pre = [-1 for i in range(N)]
	Q = [(0, S)]
	dist[S] = 0
	while Q:
		(minD, minV) = heapq.heappop(Q)
		if not visited[minV]:
			for i in G[minV]:
				if G[minV][i] < dist[i] and (not visited[i]):
					dist[i] = G[minV][i]
					heapq.heappush(Q, (dist[i], i))
					pre[i] = minV
			visited[minV] = True
	print(sum(dist))

def update(V, X, Y, R):
	if Y not in V[X]:
		V[X][Y] = R
	else:
		V[X][Y] = min(V[X][Y], R)
(n, m) = map(int, input().split())
g = [dict() for x in range(n)]
for i in range(m):
	(X, Y, R) = (int(x) for x in input().split())
	(X, Y) = (X - 1, Y - 1)
	update(g, X, Y, R)
	update(g, Y, X, R)
Pmst(g, n, int(input()) - 1)


class UF:

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

	def union(self, a, b):
		self.par[self.find(a)] = b

	def find(self, a):
		while self.par[a] != a:
			a = self.par[a]
		return a
(V, E) = [int(n) for n in input().split()]
edges = []
for _ in range(E):
	(a, b, v) = list(map(int, input().split()))
	edges.append((a - 1, b - 1, v))
input()
u = UF(V)
edges.sort(key=lambda e: e[2])
s = 0
for (a, b, v) in edges:
	if u.find(a) != u.find(b):
		s += v
		u.union(a, b)
print(s)


class Edge:

	def __init__(self, metadata):
		(self.nodeA, self.nodeB, self.weight) = metadata.split()
		self.weight = int(self.weight)

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

	def __add__(self, other):
		return self.weight + other.weight

	def __rad__(self, other):
		return self + other
(v, e) = list(map(int, input().split()))
edges = []
vertices = set()
for ii in range(1, v + 1):
	vertices.add(str(ii))
for ii in range(e):
	edges.append(Edge(input()))
edges = sorted(edges)
start = input()
included_vertices = set()
vertices.remove(start)
answer = 0
while not len(vertices) == 0:
	for edge in edges:
		if edge.nodeA not in vertices and edge.nodeB not in vertices:
			del edge
		elif edge.nodeA in vertices and edge.nodeB in vertices:
			continue
		else:
			answer += edge.weight
			included_vertices.add(edge.nodeA)
			included_vertices.add(edge.nodeB)
			if edge.nodeA in vertices:
				vertices.remove(edge.nodeA)
			if edge.nodeB in vertices:
				vertices.remove(edge.nodeB)
			break
print(answer)


import heapq
from heapq import heappush, heappop

def prim(x_to_ys_dict, S, xy_to_edgelen_dict):
	q = []
	for y in x_to_ys_dict[S]:
		heappush(q, (xy_to_edgelen_dict[S, y], S, y))
	visited = set([S])
	ret = 0
	while q:
		(edgelen, x, y) = heappop(q)
		if not y in visited and x in visited:
			ret += xy_to_edgelen_dict[x, y]
			visited.add(y)
			for neighbor in x_to_ys_dict[y] - visited:
				heappush(q, (xy_to_edgelen_dict[y, neighbor], y, neighbor))
	return ret
(N, M) = tuple([int(x) for x in input().strip().split()])
x_to_ys_dict = dict()
xy_to_edgelen_dict = dict()
for i in range(N):
	x_to_ys_dict[i + 1] = set()
for _ in range(M):
	(x, y, dist) = tuple([int(x) for x in input().strip().split()])
	x_to_ys_dict[x].add(y)
	x_to_ys_dict[y].add(x)
	xy_to_edgelen_dict[x, y] = min(xy_to_edgelen_dict[x, y], dist) if (x, y) in xy_to_edgelen_dict else dist
	xy_to_edgelen_dict[y, x] = min(xy_to_edgelen_dict[y, x], dist) if (y, x) in xy_to_edgelen_dict else dist
S = int(input())
print(prim(x_to_ys_dict, S, xy_to_edgelen_dict))


import queue
[N, M] = [int(i) for i in input().split()]
adj = [list() for i in range(N)]
graph = [0] * N
for i in range(M):
	(a, b, v) = tuple([int(i) for i in input().split()])
	node = (v, a, b)
	adj[a - 1].append(node)
	adj[b - 1].append(node)
total = 0
s = int(input())
graph[s - 1] = 1
Q = queue.PriorityQueue()
for i in adj[s - 1]:
	Q.put(i)
while sum(graph) != N:
	while not Q.empty():
		x = Q.get()
		a = x[1]
		b = x[2]
		if not graph[a - 1]:
			total += x[0]
			graph[a - 1] = 1
			for i in adj[a - 1]:
				Q.put(i)
			break
		if not graph[b - 1]:
			total += x[0]
			graph[b - 1] = 1
			for i in adj[b - 1]:
				Q.put(i)
			break
print(total)


inf = float('inf')

def allConnected(connected):
	for b in connected:
		if b == 0:
			return False
	return True
(n, m) = map(int, input().split())
edges = [[inf for j in range(n)] for i in range(n)]
for i in range(m):
	(u, v, r) = map(int, input().split())
	edges[u - 1][v - 1] = min(r, edges[u - 1][v - 1])
	edges[v - 1][u - 1] = min(r, edges[v - 1][u - 1])
curr_node = int(input()) - 1
connected = [0 for i in range(n)]
values = [inf for i in range(n)]
values[curr_node] = 0
sum = 0
while not allConnected(connected):
	(node, min_value) = (None, inf)
	for i in range(len(values)):
		if connected[i] == 0 and values[i] < min_value:
			(node, min_value) = (i, values[i])
	connected[node] = 1
	sum += min_value
	for i in range(len(edges[node])):
		if edges[node][i] < values[i]:
			values[i] = edges[node][i]
print(sum)


from heapq import heappush, heappop
import sys

class Graph(object):

	def __init__(self, N):
		self.N = N
		self.adjMatrix = [-1] * N
		for i in range(N):
			self.adjMatrix[i] = [-1] * N

	def addEdge(self, a, b, c):
		if self.adjMatrix[a - 1][b - 1] >= 0:
			self.adjMatrix[a - 1][b - 1] = min(self.adjMatrix[a - 1][b - 1], c)
		else:
			self.adjMatrix[a - 1][b - 1] = c
		self.adjMatrix[b - 1][a - 1] = self.adjMatrix[a - 1][b - 1]

	def neighbors(self, a):
		result = []
		for x in range(self.N):
			if self.adjMatrix[a][x] >= 0:
				result.append(x)
		return result

def MSTPrim(N, graph, root):
	checker = [False] * N
	minKey = [sys.maxsize] * N
	minKey[root] = 0
	heap = []
	count = 0
	heappush(heap, (0, root))
	last = None
	total = 0
	while count < N:
		(key, next) = heappop(heap)
		while checker[next]:
			(key, next) = heappop(heap)
		checker[next] = True
		count += 1
		total += key
		last = next
		for v in graph.neighbors(next):
			if not checker[v]:
				if graph.adjMatrix[v][next] < minKey[v]:
					heappush(heap, (graph.adjMatrix[v][next], v))
					minKey[v] = graph.adjMatrix[v][next]
	return total
(n, e) = input().split()
(n, e) = (int(n), int(e))
G = Graph(n)
for j in range(e):
	(a, b, c) = input().split()
	(a, b, c) = (int(a), int(b), int(c))
	G.addEdge(a, b, c)
root = int(input())
print(MSTPrim(n, G, root - 1))


class Edge:

	def __init__(self, node1, node2, weight):
		self.node1 = node1 if node1 < node2 else node2
		self.node2 = node2 if node1 < node2 else node1
		self.weight = weight

	def __eq__(self, other):
		if self.node1 == other.node1 and self.node2 == other.node2 and (self.weight == other.weight):
			return True
		elif self.node1 == other.node2 and self.node2 == other.node1 and (self.weight == other.weight):
			return True
		else:
			return False

	def __str__(self):
		return '[{}, {}]: {}'.format(self.node1, self.node2, self.weight)

class DirEdge:

	def __init__(self, node1, node2, weight):
		self.node1 = node1
		self.node2 = node2
		self.weight = weight

	def __cmp__(self, other):
		if self.node1 == other.node1 and self.node2 == other.node2 and (self.weight == other.weight):
			return 0
		elif self.node1 == other.node2 and self.node2 == other.node1 and (self.weight == other.weight):
			return 0
		else:
			return 1

	def __str__(self):
		return '[{}, {}]: {}'.format(self.node1, self.node2, self.weight)

class Graph:

	def __init__(self, nnodes):
		self.nnodes = nnodes
		self.nedges = 0
		self._graph = [[] for n in range(nnodes)]

	def add_edge(self, node1, node2, weight):
		nedge = Edge(node1, node2, weight)
		if not self.has_edge(nedge):
			self._graph[node1].append(nedge)
			self._graph[node2].append(nedge)
			self.nedges += 1

	def has_edge(self, edge):
		for e in self._graph[edge.node1]:
			if e == edge:
				return True
		return False

	def get_edges(self, node):
		return self._graph[node]

def prim(graph, snode):
	cnode = snode
	mst = []
	mstns = set()
	bag_of_paths = []
	while True:
		ncnodes = set()
		for edge in graph.get_edges(cnode):
			s = edge.node1 if edge.node1 == cnode else edge.node2
			e = edge.node2 if edge.node1 == cnode else edge.node1
			w = edge.weight
			de = DirEdge(s, e, w)
			if e not in mstns:
				bag_of_paths.append(de)
				ncnodes.add(cnode)
		bag_of_paths = [path for path in bag_of_paths if path.node2 not in mstns]
		bag_of_paths.sort(key=lambda p: p.weight)
		path = bag_of_paths.pop(0)
		mst.append(path)
		mstns.add(path.node1)
		mstns.add(path.node2)
		ncnodes.add(path.node2)
		if len(mst) == graph.nnodes - 1:
			break
		cnode = path.node2
	return mst
(nnodes, nedges) = tuple([int(n) for n in input().strip().split(' ')])
graph = Graph(nnodes)
for ne in range(nedges):
	(snode, enode, weight) = tuple([int(n) for n in input().strip().split(' ')])
	graph.add_edge(snode - 1, enode - 1, weight)
snode = int(input()) - 1
gweight = 0
for edge in prim(graph, snode):
	gweight += edge.weight
print(gweight)


import math
import sys

def findmin(known, dv, pv):
	list1 = [[i, dv[i]] for i in range(node) if known[i] is not 1 and dv[i] is not float('inf')]
	list1.sort(key=lambda x: x[1])
	if len(list1) is 0:
		return 'completed'
	return list1[0][0]
(node, edges) = input().split()
node = int(node)
edges = int(edges)
matrix = []
for m in range(node):
	temp = []
	for n in range(node):
		temp.append(float('inf'))
	matrix.append(temp)
for x in range(edges):
	(x, y, dist) = input().split()
	(x, y, dist) = (int(x), int(y), int(dist))
	if matrix[x - 1][y - 1] > dist:
		matrix[x - 1][y - 1] = dist
		matrix[y - 1][x - 1] = dist
source = int(input())
dv = [float('inf') for i in range(node)]
pv = [0 for i in range(node)]
known = [0 for i in range(node)]
known[source - 1] = 1
dv[source - 1] = 0
pv[source - 1] = 0
length = 0
ele = source - 1
while True:
	for i in range(node):
		if known[i] == 0:
			if matrix[ele][i] < dv[i]:
				dv[i] = matrix[ele][i]
				pv[i] = ele
	min = findmin(known, dv, pv)
	if min is 'completed':
		break
	known[min] = 1
	ele = min
sum = 0
for i in range(node):
	sum += dv[i]
print(sum)


(n, m) = map(int, input().strip().split())
edges = []
import heapq
visited = set()
for i in range(m):
	(i, j, w) = map(int, input().strip().split())
	heapq.heappush(edges, (w, i, j))
cache = []
(w, i, j) = heapq.heappop(edges)
count = w
visited.add(i)
visited.add(j)
while edges:
	(w, i, j) = heapq.heappop(edges)
	if i in visited and j in visited:
		continue
	elif i not in visited and j not in visited:
		cache.append((w, i, j))
	else:
		count += w
		visited.add(i)
		visited.add(j)
		edges.extend(cache)
		cache = []
		heapq.heapify(edges)
print(count)


(n, m) = list(map(int, input().split(' ')))
edges = [[] for x in range(n)]
nodes = [x for x in range(n)]
for x in range(m):
	(a, b, r) = list(map(int, input().split(' ')))
	edges[a - 1].append([b - 1, r])
	edges[b - 1].append([a - 1, r])
s = int(input()) - 1
sub_nodes_enum = [s]
sub_nodes_bool = [False for x in range(n)]
sub_nodes_bool[s] = True
weight = 0
while True:
	min_volume = -1
	min_index = -1
	for x in sub_nodes_enum:
		for y in edges[x]:
			if not sub_nodes_bool[y[0]]:
				if y[1] < min_volume or min_volume == -1:
					min_volume = y[1]
					min_index = y[0]
	if min_volume != -1:
		sub_nodes_enum.append(min_index)
		sub_nodes_bool[min_index] = True
		weight += min_volume
	if len(sub_nodes_enum) == n:
		break
print(weight)


import heapq as pq

class WeightedGraph:

	def __init__(self, n):
		self._size = n
		self._edges = [None] * n

	def __len__(self):
		return self._size

	def __setitem__(self, edge, label):
		(u, v) = edge
		for (a, b) in [(u, v), (v, u)]:
			a -= 1
			if self._edges[a]:
				self._edges[a].append((label, b))
			else:
				self._edges[a] = [(label, b)]

	def __getitem__(self, node):
		return self._edges[node - 1] or []

	def __iter__(self):
		return iter(range(1, self._size + 1))

	def __str__(self):
		return '\n'.join(('%2d -> %s' % (i, str(self[i])) for i in self))

def smallest_subtree(graph, start):
	frontier = [(0, start)]
	seen = set()
	total_weight = 0
	while frontier:
		(weight, current) = pq.heappop(frontier)
		if current not in seen:
			seen.add(current)
			total_weight += weight
			for (w, n) in graph[current]:
				if n not in seen:
					pq.heappush(frontier, (w, n))
	return total_weight
(n, m) = map(int, input().split())
g = WeightedGraph(n)
while m > 0:
	m -= 1
	(x, y, r) = map(int, input().split())
	g[x, y] = r
s = int(input())
print(smallest_subtree(g, s))


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

def merge(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		if c[x] > c[y]:
			p[y] = x
			c[x] += c[y]
		else:
			p[x] = y
			c[y] += c[x]
(n, m) = map(int, input().split())
p = list(range(n))
c = [1] * n
e = []
for _ in range(m):
	(x, y, r) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	if x > y:
		(x, y) = (y, x)
	e.append((r, x, y))
e = sorted(e)
s = 0
i = 0
r = 0
while i < m and s < n - 1:
	x = find(e[i][1])
	y = find(e[i][2])
	if x != y:
		merge(x, y)
		r += e[i][0]
		s += 1
	i += 1
print(r)


import queue as q
(n, m) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(x, y, r) = map(int, input().split())
	adj[x - 1].append((r, y - 1))
	adj[y - 1].append((r, x - 1))
s = int(input()) - 1
visit = [0] * n
visit[s] = 1
pq = q.PriorityQueue()
total = 0
for i in adj[s]:
	pq.put(i)
while not pq.empty():
	(r, v) = pq.get()
	while visit[v] == 1 and (not pq.empty()):
		(r, v) = pq.get()
	if visit[v] == 0:
		visit[v] = 1
		total = total + r
		for i in adj[v]:
			if visit[i[1]] == 0:
				pq.put(i)
print(total)


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Prims:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		value = 0
		visited = [-1] * len(self.graph.get_vertices().keys())
		visited[start - 1] = 0
		edges = self.convert_edges(self.graph.get_vertex(start).get_edges())
		while len(edges) > 0:
			index = self.findmin(edges)
			(node, weight) = edges[index]
			if visited[node - 1] == -1:
				del edges[index]
				visited[node - 1] = 0
				value += weight
				edges_new = self.convert_edges(self.graph.get_vertex(node).get_edges())
				for i in edges_new:
					if visited[i[0] - 1] == -1:
						edges.append(i)
			else:
				del edges[index]
		return value

	def findmin(self, edges):
		mins = edges[0][1]
		index = 0
		for i in range(1, len(edges)):
			if edges[i][1] < mins:
				mins = edges[i][1]
				index = i
		return index

	def convert_edges(self, edges):
		edgess = []
		for key in edges.keys():
			edgess.append((int(key), int(edges[key])))
		return edgess

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

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

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Prims(graph)
	S = int(sys.stdin.readline())
	minimum_weight = dijkstra.calculate(S)
	print(minimum_weight)
execute_test_case()


from queue import PriorityQueue

def get_edges(V, data):
	edges = [d for d in data if d[0] == V or d[1] == V]
	return edges

def prim_total_weight(N, M, S, data):
	all_nodes = set(list(range(1, N + 1)))
	V = S
	nodes = set()
	nodes.update([V])
	pq = PriorityQueue(maxsize=M)
	summation = 0
	while nodes != all_nodes:
		edges = get_edges(V, data)
		for edge in edges:
			if not set(edge[0:2]).issubset(nodes):
				pq.put((edge[2], edge))
		lowest = None
		while not lowest:
			get = pq.get(False)[1]
			set_get = set(get[0:2])
			new_node = set_get.difference(set_get.intersection(nodes))
			if not set_get.issubset(nodes) and new_node:
				lowest = get[0:3]
				V = new_node.pop()
				nodes.update([V])
		summation += lowest[2]
	return summation
(N, M) = map(int, input().split())
data = []
for line in range(M):
	data.append(list(map(int, input().split())))
S = int(input())
print(prim_total_weight(N, M, S, data))


import heapq as pq
(N, M) = map(int, input().split(' '))
graph = {}
todo = set()
w = {}
for i in range(1, N + 1):
	graph[i] = []
	todo.add(i)
for _ in range(M):
	(x, y, c) = map(int, input().split(' '))
	graph[x].append(y)
	graph[y].append(x)
	w[x, y] = c
	w[y, x] = c
mst = 0
root = int(input())
heap = [(0, root)]
while todo and heap:
	(c, n) = pq.heappop(heap)
	if n in todo:
		mst += c
		todo.remove(n)
	for child in graph[n]:
		if child in todo:
			pq.heappush(heap, (w[n, child], child))
print(mst)


import collections
import sys
import heapq
(N, M) = map(int, sys.stdin.readline().split(' '))
edges = collections.defaultdict(dict)
q = []
for i in range(M):
	(x, y, S) = map(int, sys.stdin.readline().split(' '))
	edges[x][y] = S
	edges[y][x] = S
connected = set()
(S, node) = (0, 1)
heapq.heappush(q, (S, node))
total = 0
while len(q) > 0:
	(S, node) = heapq.heappop(q)
	if node in connected:
		continue
	total += S
	connected.add(node)
	for (other, S) in edges[node].items():
		if other not in connected:
			heapq.heappush(q, (S, other))
print(total)


from heapq import *

class node(object):

	def __init__(self, name, color='w', edges={}):
		self.name = name
		self.color = color
		self.edges = edges

	def reset(self):
		self.color = 'w'
		self.edges = {}
		self.position = float('inf')
		self.predecesor = None
		self.distanceToS = float('inf')

def MST(graph, s):
	graph[s].color = 'b'
	Total = 0
	B = []
	H = []
	minAt = s
	graph[s].color = 'b'
	while len(B) < len(graph):
		B += [minAt]
		for a in graph[minAt].edges.keys():
			if graph[a].color != 'b':
				heappush(H, (graph[minAt].edges[a], [minAt, a]))
		if len(H) > 0:
			while True:
				if len(H) == 0:
					break
				minInf = heappop(H)
				if graph[minInf[1][0]].color != 'b':
					graph[minInf[1][0]].color = 'b'
					Total += minInf[0]
					minAt = minInf[1][1]
					break
				elif graph[minInf[1][1]].color != 'b':
					graph[minInf[1][1]].color = 'b'
					Total += minInf[0]
					minAt = minInf[1][1]
					break
	return Total
(n, m) = [int(x) for x in input().split()]
graph = [node(i) for i in range(n)]
for a in graph:
	a.reset()
for _ in range(m):
	(a, b, r) = [int(x) for x in input().split()]
	a = a - 1
	b = b - 1
	if b in graph[a].edges.keys():
		if graph[a].edges[b] > r:
			graph[a].edges[b] = r
			graph[b].edges[a] = r
	else:
		graph[a].edges[b] = r
		graph[b].edges[a] = r
s = int(input())
s = s - 1
print(MST(graph, s))


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, vertex, distance):
		if vertex not in self.edges or distance < self.edges[vertex]:
			self.edges[vertex] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, key):
		return self.vertices[key]

	def add_vertex(self, key, vertex):
		self.vertices[key] = vertex

class Prim:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self):
		visited = set()
		vertices = queue.PriorityQueue()
		vertices.put((0, 1))
		ans = 0
		while not vertices.empty():
			(cost, vertex) = vertices.get()
			if vertex in visited:
				continue
			visited.add(vertex)
			ans += cost
			self.update_vertices(vertex, visited, vertices)
		return ans

	def update_vertices(self, parent, visited, vertices):
		edges = self.graph.get_vertex(parent).get_edges()
		for (vertex, cost) in edges.items():
			if vertex in visited:
				continue
			vertices.put((cost, vertex))

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

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	prim = Prim(graph)
	S = int(sys.stdin.readline())
	ans = prim.calculate()
	print(ans)

def main():
	execute_test_case()
main()


from collections import defaultdict

class Graph:
	adj_list = []
	parent = []
	key_value = defaultdict()
	q = defaultdict(dict)

	def __init__(self, V):
		for i in range(0, V):
			self.adj_list.append([i])
		for i in range(0, V):
			self.key_value[i] = 999999

	def add_Edge(self, u, v, r):
		self.adj_list[u].append([v, r])
		self.adj_list[v].append([u, r])

	def extract_min(self):
		min = 9999999
		ii = 0
		for (key, value) in self.q.items():
			if min > value:
				min = value
				ii = key
		del self.q[ii]
		return ii

	def Prim(self, s):
		self.key_value[s] = 0
		self.q = self.key_value.copy()
		k = len(self.q)
		while k:
			u = self.extract_min()
			for i in range(1, len(self.adj_list[u])):
				if self.adj_list[u][i][0] in self.q and self.adj_list[u][i][1] < self.key_value[self.adj_list[u][i][0]]:
					self.key_value[self.adj_list[u][i][0]] = self.adj_list[u][i][1]
					self.q[self.adj_list[u][i][0]] = self.adj_list[u][i][1]
			k = k - 1

	def sum_of_edges(self):
		sum = 0
		for (key, value) in self.key_value.items():
			sum = sum + value
		print(sum)
(V, E) = map(int, input().split())
g = Graph(V)
for _ in range(0, E):
	(x, y, r) = map(int, input().split())
	g.add_Edge(x - 1, y - 1, r)
s = int(input())
g.Prim(s - 1)
g.sum_of_edges()


(n, m) = input().split()
(n, m) = (int(n), int(m))
graph = dict()
for i in range(m + 1):
	graph[i + 1] = set()
for i in range(m):
	(st, end, val) = list(map(int, input().split()))
	graph[st].add((end, val))
	graph[end].add((st, val))
start = int(input())
visited = set()
visited.add(start)
length = 0
while len(visited) < n:
	potential_edges = set()
	for node in visited:
		for edge in graph[node]:
			if edge[0] not in visited:
				potential_edges.add((node, edge[1], edge[0]))
	min_edge = min(potential_edges, key=lambda x: x[1])
	visited.add(min_edge[2])
	length += min_edge[1]
print(length)


class Edge:

	def __init__(self, n1, n2, v):
		if n1.id <= n2.id:
			self.n1 = n1
			self.n2 = n2
		else:
			self.n1 = n2
			self.n2 = n1
		self.v = v
		n1.neighbor.append(self)
		n2.neighbor.append(self)

	def to(self, n):
		if n == self.n1:
			return self.n2
		elif n == self.n2:
			return self.n1
		else:
			raise Exception('Node is not link be this edge')

	def __repr__(self):
		return 'e({}-{})'.format(self.n1.id + 1, self.n2.id + 1)

class Node:

	def __init__(self, id):
		self.id = id
		self.neighbor = []

	def link(self, other):
		self.neighbor.add(other)
		other.neighbor.add(self)

	def unlink(self, other):
		self.neighbor.discard(other)
		other.neighbor.discard(self)

	def __eq__(self, other):
		return self.id == other.id

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

	def __hash__(self):
		return hash(self.id)

	def __repr__(self):
		return 'id:{},nb:{}'.format(self.id + 1, self.neighbor)

class Vnode:

	def __init__(self, node, r=float('inf')):
		self.node = node
		self.r = r

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

	def __hash__(self):
		return hash(self.node)

	def __repr__(self):
		return 'id:{},v:{}'.format(self.node.id + 1, self.r)
import heapq
for _ in range(1):
	(n, m) = map(int, input().split())
	l = [Node(_) for _ in range(n)]
	a = [Vnode(_) for _ in l]
	for _ in range(m):
		(n1, n2, v) = map(int, input().split())
		Edge(l[n1 - 1], l[n2 - 1], v)
	s = int(input()) - 1
	c = l[s]
	a[c.id].r = 0
	h = [a[c.id]]
	v = set()
	while len(h):
		ca = heapq.heappop(h)
		c = ca.node
		r = ca.r
		v.add(c)
		h = set(h)
		for nbe in c.neighbor:
			nb = nbe.to(c)
			if nb not in v:
				a[nb.id].r = min(a[nb.id].r, nbe.v)
				h.add(a[nb.id])
		h = list(h)
		heapq.heapify(h)
	print(sum([x.r for x in a]))


from collections import deque

def iscycle(t):
	v = [0 for i in range(n + 1)]
	par = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if v[i] == 0 and i in d:
			if dfs(i, v, par, t):
				return True
	return False

def dfs(i, v, par, t):
	q = deque([i])
	while q:
		u = q.pop()
		if v[u] == 1:
			continue
		v[u] = 1
		if u in t:
			for y in t[u]:
				if par[y] != 0 and par[u] != y and (par[y] != u):
					return True
				if v[y] == 0:
					q.append(y)
					par[y] = u
	return False
(n, m) = [int(x) for x in input().strip().split()]
d = dict()
w = [[0, 0, 0] for i in range(m)]
for i in range(m):
	(u, v, y) = [int(x) for x in input().strip().split()]
	w[i][0] = y
	w[i][1] = u
	w[i][2] = v
s = int(input().strip())
w.sort()
cnt = 0
wt = 0
for i in range(m):
	if cnt == n - 1:
		break
	u = w[i][1]
	v = w[i][2]
	if u in d:
		if v not in d[u]:
			d[u].append(v)
		else:
			continue
	else:
		d[u] = [v]
	if v in d:
		d[v].append(u)
	else:
		d[v] = [u]
	if not iscycle(d):
		cnt = cnt + 1
		wt = wt + w[i][0]
	else:
		d[u].remove(v)
		if not d[u]:
			del d[u]
		d[v].remove(u)
		if not d[v]:
			del d[v]
print(wt)


import heapq

def main():
	(edge_tuples, node_count) = read_test_case()
	graph = read_in_graph(edge_tuples, node_count)
	starting_point = int(input())
	print(compute_msp_prim(graph, starting_point))

def read_test_case():
	line = input()
	node_count = line.split()[0]
	edge_count = line.split()[1]
	edge_tuples = []
	for edge in range(int(edge_count)):
		new_edge = input()
		(first_node, second_node, distance) = new_edge.split()
		edge_tuples.append((int(first_node), int(second_node), int(distance)))
	return (edge_tuples, int(node_count))

def read_in_graph(edges, node_count):
	adjacency_list = {}
	for node in range(1, node_count + 1):
		adjacency_list[node] = []
	for edge in edges:
		adjacency_list[edge[0]].append((edge[1], edge[2]))
		adjacency_list[edge[1]].append((edge[0], edge[2]))
	return adjacency_list

def compute_msp_prim(graph, starting_point):
	visited = set()
	edges = []
	overall_distance = 0
	heapq.heappush(edges, (0, starting_point))
	while edges:
		(distance, node) = heapq.heappop(edges)
		if node not in visited:
			overall_distance += distance
			update_edges(node, visited, edges, graph)
	return overall_distance

def update_edges(node, visited, edges, graph):
	visited.add(node)
	for (child, dist) in graph[node]:
		if child not in visited:
			heapq.heappush(edges, (dist, child))
main()


from collections import defaultdict
SOMETHING_BIG = 100000000000
(node_count, edge_count) = [int(x) for x in input().split()]
edges = defaultdict(list)
nodes = list(range(1, node_count + 1))
for _ in range(0, edge_count):
	(l, r, c) = [int(x) for x in input().split()]
	edges[l].append((r, c))
	edges[r].append((l, c))
start = int(input())
C = defaultdict(lambda : SOMETHING_BIG)
E = defaultdict(lambda : None)
F = ([], [])
Q = set(nodes)

def get_min(items, scores):
	smallest_score = SOMETHING_BIG
	smallest_item = None
	for item in items:
		if scores[item] < smallest_score:
			smallest_score = scores[item]
			smallest_item = item
	return smallest_item

def do_step(v):
	Q.remove(v)
	F[0].append(v)
	if E[v]:
		F[1].append(E[v])
	for (w, cost) in edges[v]:
		if C[w] > cost:
			C[w] = cost
			E[w] = [v, w, cost]
do_step(start)
while Q:
	v = get_min(Q, C)
	do_step(v)
total_cost = sum([cost for (x, y, cost) in F[1]])
print(total_cost)


(nodes, edges) = map(int, input().strip().split())
graph = dict()
total_weight = 0
mst = set()
for _ in range(edges):
	(x, y, weight) = map(int, input().strip().split())
	if x not in graph:
		graph[x] = []
	graph[x].append((y, weight))
	if y not in graph:
		graph[y] = []
	graph[y].append((x, weight))
S = int(input().strip())
edges = dict()

def compute_new_edges(node):
	for node in graph[node]:
		if node[0] not in mst:
			if node[0] not in edges:
				edges[node[0]] = node[1]
			elif node[1] < edges[node[0]]:
				edges[node[0]] = node[1]
mst.add(S)
compute_new_edges(S)
while len(mst) < nodes:
	smallest_weight = 99999999999
	smallest_node = 0
	for (node, weight) in edges.items():
		if weight < smallest_weight:
			smallest_weight = weight
			smallest_node = node
	total_weight += smallest_weight
	mst.add(smallest_node)
	del edges[smallest_node]
	compute_new_edges(smallest_node)
print(total_weight)


import sys

def MST(m, E, s):
	V = {}
	s = s - 1
	for i in range(m):
		V[i] = []
	for j in range(len(E)):
		V[E[j][0] - 1].append(E[j][1] - 1)
		V[E[j][1] - 1].append(E[j][0] - 1)
		V[E[j][0] - 1].append(E[j][2])
		V[E[j][1] - 1].append(E[j][2])
	cur_cost = [100000 for i in range(m)]
	cur_cost[s] = 0
	unvisited_cost = []
	unvisited_cost.append(0)
	total = 0
	while len(unvisited_cost) > 0:
		sel_v = cur_cost.index(min(unvisited_cost))
		total += min(unvisited_cost)
		unvisited_cost.remove(min(unvisited_cost))
		i = 0
		while i < len(V[sel_v]):
			sel_n = V[sel_v][i]
			ew = V[sel_v][i + 1]
			i += 2
			if cur_cost[sel_n] > ew:
				if cur_cost[sel_n] in unvisited_cost:
					unvisited_cost.remove(cur_cost[sel_n])
				cur_cost[sel_n] = min(cur_cost[sel_n], ew)
				unvisited_cost.append(cur_cost[sel_n])
		cur_cost[sel_v] -= 351 * 3 * m
	for i in range(m):
		if cur_cost[i] == 350 * (m + 1):
			cur_cost[i] = -1
		else:
			cur_cost[i] += 351 * 3 * m
		cur_cost[i] = str(cur_cost[i])
	cur_cost.remove('0')
	print(total)
	return
t = 1
for i in range(t):
	E = []
	(m, n) = input().strip().split(' ')
	m = int(m)
	n = int(n)
	for j in range(n):
		(m1, n1, v1) = input().strip().split(' ')
		m1 = int(m1)
		n1 = int(n1)
		v1 = int(v1)
		E.append([n1, m1, v1])
	n1 = input().strip()
	n1 = int(n1)
	MST(m, E, n1)


from queue import PriorityQueue as pq
INF = float('inf')
(N, M) = [int(i) for i in input().split(' ')]
weights = {}
neighbors = [[] for i in range(N)]
for i in range(M):
	(x, y, r) = [int(i) for i in input().split(' ')]
	x -= 1
	y -= 1
	edge = None
	if x < y:
		edge = (x, y)
	else:
		edge = (y, x)
	if edge not in weights:
		neighbors[x].append(y)
		neighbors[y].append(x)
		weights[edge] = r
	elif r < weights[edge]:
		weights[edge] = r
S = int(input()) - 1
q = pq()
reached = [False for i in range(N)]
dist = [INF for i in range(N)]
tos = [None for i in range(N)]
dist[S] = 0
for i in range(N):
	q.put((dist[i], i))
while not q.empty():
	item = q.get()
	n = item[1]
	if not reached[n]:
		reached[n] = True
		for nn in neighbors[n]:
			if not reached[nn]:
				w = 0
				if nn < n:
					w = weights[nn, n]
				else:
					w = weights[n, nn]
				if w < dist[nn]:
					dist[nn] = w
					q.put((w, nn))
print(sum(dist))


l = input().split()
N = int(l[0])
M = int(l[1])
edges = [[] for m in range(N + 1)]
for m in range(M):
	l = input().split()
	x = int(l[0])
	y = int(l[1])
	r = int(l[2])
	edges[x].append((y, r))
	edges[y].append((x, r))
S = int(input())
in_tree = {S}
weight = 0
possibilities = sorted(edges[S], key=lambda x: x[1])
while len(in_tree) < N:
	while possibilities[0][0] in in_tree:
		possibilities.pop(0)
	in_tree.add(possibilities[0][0])
	weight += possibilities[0][1]
	possibilities += edges[possibilities[0][0]]
	possibilities.sort(key=lambda x: x[1])
print(weight)


line = input().strip().split()
n = int(line[0])
m = int(line[1])
unvisited = set()
for x in range(n):
	unvisited.add(x + 1)
edges = []
for i in range(m):
	edges.append([int(x) for x in input().strip().split()])
s = int(input().strip())
edges.sort(key=lambda edge: edge[2])
unvisited.remove(s)
total_weight = 0
while len(unvisited) > 0:
	i = 0
	while i < len(edges):
		edge = edges[i]
		uv0 = edge[0] in unvisited
		uv1 = edge[1] in unvisited
		if uv0 and uv1:
			i += 1
		elif not uv0 and (not uv1):
			edges.pop(i)
		else:
			if uv0:
				unvisited.remove(edge[0])
			if uv1:
				unvisited.remove(edge[1])
			total_weight += edge[2]
			edges.pop(i)
			break
print(total_weight)


from heapq import heapify, heappush, heappop

def prim_mst(graph, start):
	(visited, nodes) = (set(), set([i for i in graph]))
	(tree, tree_weight) = ({i: set() for i in graph}, 0)
	edge_choices = [(0, None, start)]
	tree[None] = set()
	heapify(edge_choices)
	while nodes:
		(weight, src, dest) = heappop(edge_choices)
		if not dest in visited:
			tree[src].add((dest, weight))
			tree[dest].add((src, weight))
			nodes.remove(dest)
			visited.add(dest)
			tree_weight += weight
			for neighbour in graph[dest]:
				if not neighbour[0] in visited:
					heappush(edge_choices, (neighbour[1], dest, neighbour[0]))
	return (tree, tree_weight)
(n, m) = [int(i) for i in input().split()]
graph = {i + 1: set() for i in range(n)}
for i in range(m):
	edge = [int(j) for j in input().split()]
	graph[edge[0]].add((edge[1], edge[2]))
	graph[edge[1]].add((edge[0], edge[2]))
start = int(input())
print(prim_mst(graph, start)[1])


class Node(object):

	def __init__(self, name):
		self.name = name
		self.neighbors = {}

	def __str__(self):
		return str(self.name) + ' -> ' + str(self.neighbors) + '\n'

class Graph(object):

	def __init__(self, nodes, edges):
		self.nodes = []
		self.num_nodes = nodes
		self.num_edges = edges
		for i in range(nodes + 1):
			self.add_node(i)

	def add_node(self, name):
		new_node = Node(name)
		self.nodes.append(new_node)

def get_path(start, g, visited, path):
	visited = []
	visited.append(start)
	total = 0
	path = g.nodes[start]
	while len(visited) != g.num_nodes:
		node_to_visit = min(g.nodes[start].neighbors, key=g.nodes[start].neighbors.get)
		if not node_to_visit in visited:
			visited.append(node_to_visit)
			weight = g.nodes[start].neighbors[node_to_visit]
			del path.neighbors[node_to_visit]
			for node in g.nodes[node_to_visit].neighbors:
				if node in path.neighbors and node not in visited:
					if g.nodes[node_to_visit].neighbors[node] < path.neighbors[node]:
						v = g.nodes[node_to_visit].neighbors[node]
						u = path.neighbors[node]
						path.neighbors[node] = g.nodes[node_to_visit].neighbors[node]
				elif not node in visited:
					path.neighbors[node] = g.nodes[node_to_visit].neighbors[node]
			total = total + weight
		elif node_to_visit in visited:
			del path.neighbors[node_to_visit]
	return total

def main():
	(nodes, edges) = map(int, input().split())
	g = Graph(nodes, edges)
	for i in range(edges):
		(x, y, r) = map(int, input().split())
		g.nodes[x].neighbors[y] = r
		g.nodes[y].neighbors[x] = r
	start = int(input())
	print(str(get_path(start, g, [], {})))
main()


class DisjointSet:
	s = list()

	def __init__(self, length):
		self.length = length
		for i in range(length):
			self.s.append(-1)

	def find(self, val):
		if self.s[val] < 0:
			return val
		else:
			return self.find(self.s[val])

	def union(self, root1, root2):
		root1 = self.find(root1)
		root2 = self.find(root2)
		if self.s[root1] > self.s[root2]:
			self.s[root1] = root2
		elif self.s[root1] < self.s[root2]:
			self.s[root2] = root1
		else:
			self.s[root1] -= 1
			self.s[root2] = root1

class Vertex:
	inTree = False
	adj = list()

	def __init__(self, id):
		self.id = id

class Edge:

	def __init__(self, v1, v2, weight):
		self.v1 = v1
		self.v2 = v2
		self.weight = weight

	def __eq__(self, other):
		return self.weight == other.weight and self.v1.id + self.v2.id == other.v1.id + other.v2.id

	def __lt__(self, other):
		if self.weight < other.weight:
			return self.weight < other.weight
		elif self.weight == other.weight:
			return self.v1.id + self.v2.id < other.v1.id + other.v2.id

def runkruskal(g, s):
	res = list()
	while len(g) > 0:
		e = g[0]
		if s.find(e.v1.id) != s.find(e.v2.id):
			s.union(e.v1.id, e.v2.id)
			res.append(e)
		g.pop(0)
	sum = 0
	for i in res:
		sum += i.weight
	print(sum)
temp = input().split()
nov = int(temp[0])
noe = int(temp[1])
vertices = list()
g = list()
for i in range(nov):
	v = Vertex(i)
	vertices.append(v)
for i in range(noe):
	temp = input().split()
	v1 = int(temp[0])
	v2 = int(temp[1])
	wt = int(temp[2])
	v1 = vertices[v1 - 1]
	v2 = vertices[v2 - 1]
	e = Edge(v1, v2, wt)
	g.append(e)
s = DisjointSet(nov)
g.sort()
runkruskal(g, s)


(n, m) = list(map(int, input().split(' ')))
edges = [[] for x in range(n)]
nodes = [x for x in range(n)]
for x in range(m):
	(a, b, r) = list(map(int, input().split(' ')))
	edges[a - 1].append([b - 1, r])
	edges[b - 1].append([a - 1, r])
s = int(input()) - 1
sub_nodes_enum = [s]
sub_nodes_bool = [False for x in range(n)]
sub_nodes_bool[s] = True
weight = 0
while True:
	min_volume = -1
	min_index = -1
	for x in sub_nodes_enum:
		for y in edges[x]:
			if not sub_nodes_bool[y[0]]:
				if y[1] < min_volume or min_volume == -1:
					min_volume = y[1]
					min_index = y[0]
	if min_volume != -1:
		sub_nodes_enum.append(min_index)
		sub_nodes_bool[min_index] = True
		weight += min_volume
	if len(sub_nodes_enum) == n:
		break
print(weight)


import heapq

class Node(object):

	def __init__(self, val):
		self.val = val
		self.parent = self
		self.height = 0

def union(x, y):
	xRoot = x.parent
	yRoot = y.parent
	if xRoot.height < yRoot.height:
		xRoot.parent = yRoot
	elif yRoot.height < xRoot.height:
		yRoot.parent = xRoot
	else:
		xRoot.parent = yRoot
		yRoot.height += 1

def find(x):
	if x.parent.val != x.val:
		x.parent = find(x.parent)
	return x.parent
(N, M) = list(map(int, input().strip().split(' ')))
A = []
for m in range(M):
	(u, v, w) = list(map(int, input().strip().split(' ')))
	(u, v) = (u - 1, v - 1)
	A.append((w, u, v))
heapq.heapify(A)
Nodes = []
for i in range(N):
	Nodes.append(Node(i))
ans = 0
while A:
	(w, u, v) = heapq.heappop(A)
	if find(Nodes[u]).val != find(Nodes[v]).val:
		union(Nodes[u], Nodes[v])
		ans += w
print(ans)


(N, M) = map(int, input().strip().split())
G = {}
NT = set()
for i in range(1, N + 1):
	G[i] = {}
	G[i]['distance'] = -1
	G[i]['parent'] = None
	G[i]['neighbor'] = []
	NT.add(i)
for _ in range(M):
	(x, y, r) = map(int, input().strip().split())
	G[x]['neighbor'].append((y, r))
	G[y]['neighbor'].append((x, r))
u = int(input().strip())
NT.remove(u)
sumw = 0
while NT:
	for (v, w) in G[u]['neighbor']:
		if v in NT and (G[v]['distance'] == -1 or G[v]['distance'] > w):
			G[v]['distance'] = w
			G[v]['parent'] = u
	temp = -1
	for e in filter(lambda x: G[x]['distance'] > -1, NT):
		if temp == -1 or temp > G[e]['distance']:
			temp = G[e]['distance']
			tempv = e
	sumw += temp
	u = tempv
	NT.remove(u)
print(sumw)


import sys
file = sys.stdin
(n, m) = [int(x) for x in file.readline().split(' ')]
edges = []
for _ in range(m):
	edges.append(tuple(map(int, file.readline().split(' '))))
start = int(file.readline())

def min_edge_weight(start, edges, n_count):
	tree_nodes = {start}
	node_edges = {}
	total_weight = 0
	for edge in edges:
		(n1, n2, w) = edge
		node_edges.setdefault(n1, []).append((n2, w))
		node_edges.setdefault(n2, []).append((n1, w))

	def traverse_tree():
		for n in tree_nodes:
			yield from node_edges[n]
	while len(tree_nodes) < n_count:
		(new_node, weight) = min((n for n in traverse_tree() if n[0] not in tree_nodes), key=lambda a: a[1])
		tree_nodes.add(new_node)
		total_weight += weight
	return total_weight
print(min_edge_weight(start, edges, n))


import sys
file = sys.stdin
(n, m) = [int(x) for x in file.readline().split(' ')]
edges = []
for _ in range(m):
	edges.append(tuple(map(int, file.readline().split(' '))))
start = int(file.readline())

def min_edge_weight(start, edges, n_count):
	tree_nodes = {start}
	node_edges = {}
	total_weight = 0
	for edge in edges:
		(n1, n2, w) = edge
		node_edges.setdefault(n1, []).append((n2, w))
		node_edges.setdefault(n2, []).append((n1, w))

	def traverse_tree():
		for n in tree_nodes:
			yield from node_edges[n]
	while len(tree_nodes) < n_count:
		(new_node, weight) = min((n for n in traverse_tree() if n[0] not in tree_nodes), key=lambda a: a[1])
		tree_nodes.add(new_node)
		total_weight += weight
	return total_weight
print(min_edge_weight(start, edges, n))


__author__ = 'aiswarya'
INF = 99999999

def pop_min_index(mst_set, key_value):
	min = INF
	min_ind = -1
	for i in range(len(key_value)):
		if min > key_value[i] and mst_set[i] == 0:
			min = key_value[i]
			min_ind = i
	return min_ind

def prims_mst(G, start_node):
	mst_set = [0] * len(G)
	key_value = [INF] * len(G)
	key_value[start_node] = 0
	min_wt = 0
	mst_set[0] = 1
	while 0 in mst_set:
		add_node = pop_min_index(mst_set, key_value)
		mst_set[add_node] = 1
		min_wt = min_wt + key_value[add_node]
		for each in G[add_node].keys():
			if G[add_node][each] < key_value[each]:
				key_value[each] = G[add_node][each]
	return min_wt
line = input().split()
N = int(line[0])
M = int(line[1])
G = []
for i in range(N + 1):
	G.append({})
for each in range(M):
	line = input().split()
	v1 = int(line[0])
	v2 = int(line[1])
	wt = int(line[2])
	if v2 in G[v1]:
		if wt < G[v1][v2]:
			G[v1][v2] = wt
	else:
		G[v1][v2] = wt
	if v1 in G[v2]:
		if wt < G[v2][v1]:
			G[v2][v1] = wt
	else:
		G[v2][v1] = wt
start_node = int(input())
min_wt = prims_mst(G, start_node)
print(min_wt)


def to_ints(nodes_pair):
	return (int(nodes_pair[0]), int(nodes_pair[1]), int(nodes_pair[2]))
t = 1
for _ in range(t):
	(n, m) = (int(x) for x in input().strip().split(' '))
	nodes = [to_ints(input().strip().split(' ')) for _ in range(m)]
	s = int(input().strip())
	unvisited = {i + 1 for i in range(n)}
	infinit = float('inf')
	weights = [infinit for _ in range(n)]
	graph = [set() for _ in range(n)]
	for (x, y, r) in nodes:
		graph[x - 1].add((y, r))
		graph[y - 1].add((x, r))
	weights[s - 1] = 0
	while unvisited:
		(dist, current) = min(((weights[i - 1], i) for i in unvisited))
		unvisited.remove(current)
		if dist == infinit:
			break
		for (neighbor, r) in graph[current - 1]:
			if neighbor not in unvisited:
				continue
			if r < weights[neighbor - 1]:
				weights[neighbor - 1] = r
	print(sum((w for w in weights if w != infinit)))


import heapq
(N, M) = map(int, input().split())

class Graph:

	def __init__(self):
		self.edges = {}

	def connect(self, n1: int, n2: int, weight: int) -> None:
		self.edges.setdefault(n1, []).append((weight, n2))
		self.edges.setdefault(n2, []).append((weight, n1))

	def min_mst_weight(self) -> int:
		total_weight = 0
		visited = set()
		q = [(0, 1)]
		while q:
			(weight, node) = heapq.heappop(q)
			if node in visited:
				continue
			visited.add(node)
			total_weight += weight
			for (w, n) in self.edges.get(node, []):
				if n not in visited:
					heapq.heappush(q, (w, n))
		return total_weight
graph = Graph()
for _ in range(M):
	(x, y, r) = map(int, input().split())
	graph.connect(x, y, r)
print(graph.min_mst_weight())


from collections import defaultdict
chck = list()
total = 0
temp = 100001
(nodes, edges) = map(int, input().split())
for i in range(1, nodes + 1):
	chck.append(i)
mat = [[0 for i in range(nodes + 1)] for x in range(nodes + 1)]
for i in range(1, nodes + 1):
	for j in range(1, nodes + 1):
		if i == j:
			mat[i][j] = 0
		else:
			mat[i][j] = 100001
for i in range(edges):
	(f, t, v) = map(int, input().split())
	mat[f][t] = v
	mat[t][f] = v
cons = dict()
start = int(input())
cons = {start: 0}
while len(chck) != 0:
	temp = 100001
	temp2 = 100001
	temp1 = -1
	for (i, j) in cons.items():
		if j < temp:
			temp = j
			temp1 = i
	for k in chck:
		if mat[temp1][k] < temp2:
			temp2 = mat[temp1][k]
	for k in chck:
		if mat[temp1][k] != 100001:
			if k in cons:
				if mat[temp1][k] < cons[k]:
					cons[k] = mat[temp1][k]
			else:
				cons[k] = mat[temp1][k]
	del cons[temp1]
	chck.remove(temp1)
	total = total + temp
print(total)


(N, M) = list(map(int, input().split()))
vertices = [[] for i in range(0, N + 1)]
edges = dict()

def sorted_key(key):
	return (key[1], key[0]) if key[0] > key[1] else key
for i in range(0, M):
	(tail, head, weight) = list(map(int, input().split()))
	key = sorted_key((tail, head))
	if key not in edges:
		vertices[tail].append(key)
		vertices[head].append(key)
	edges[key] = min(edges[key], weight) if key in edges else weight
S = int(input())

def find_mst_sum(vs, es, start):

	def edge_contraction(ves, eds, edge):
		(t, h) = edge[0]
		ves[t].extend(ves[h])
		ves[t] = list(filter(lambda k: k != (t, h), ves[t]))
		del eds[t, h]
		ves[h].clear()
		for i in list(filter(lambda k: k[0] == h or k[1] == h, eds.keys())):
			new_key = sorted_key((t if i[0] == h else i[0], t if i[1] == h else i[1]))
			eds[new_key] = min(eds[new_key], eds[i]) if new_key in eds else eds[i]
			del eds[i]
		for i in range(0, len(ves)):
			for j in list(filter(lambda k: k[0] == h or k[1] == h, ves[i])):
				new_key = sorted_key((t if j[0] == h else j[0], t if j[1] == h else j[1]))
				if new_key not in ves[i]:
					ves[i].append(new_key)
				ves[i].remove(j)
	cur_node = start
	mst_sum = 0
	while len(es) > 0:
		min_edge = min(list(map(lambda e: [e] + [es[e]], vs[cur_node])), key=lambda m: m[1])
		mst_sum = mst_sum + min_edge[1]
		cur_node = min_edge[0][0]
		edge_contraction(vs, es, min_edge)
	return mst_sum
print(find_mst_sum(vertices, edges, S))


(n, m) = list(map(int, input().split(' ')))
edges = [[] for x in range(n)]
nodes = [x for x in range(n)]
for x in range(m):
	(a, b, r) = list(map(int, input().split(' ')))
	edges[a - 1].append([b - 1, r])
	edges[b - 1].append([a - 1, r])
s = int(input()) - 1
sub_nodes_enum = [s]
sub_nodes_bool = [False for x in range(n)]
sub_nodes_bool[s] = True
weight = 0
while True:
	min_volume = -1
	min_index = -1
	for x in sub_nodes_enum:
		for y in edges[x]:
			if not sub_nodes_bool[y[0]]:
				if y[1] < min_volume or min_volume == -1:
					min_volume = y[1]
					min_index = y[0]
	if min_volume != -1:
		sub_nodes_enum.append(min_index)
		sub_nodes_bool[min_index] = True
		weight += min_volume
	if len(sub_nodes_enum) == n:
		break
print(weight)


import math

def heapify(Q, i):
	l = len(Q)
	while 2 * i + 1 < l:
		if 2 * i + 2 < l:
			if Q[2 * i + 1][1] < Q[2 * i + 2][1]:
				small = 2 * i + 1
			else:
				small = 2 * i + 2
			if Q[small][1] < Q[i][1]:
				test = Q[i]
				Q[i] = Q[small]
				Q[small] = test
				i = small
			else:
				return
		elif Q[2 * i + 1][1] < Q[i][1]:
			test = Q[i]
			Q[i] = Q[2 * i + 1]
			Q[2 * i + 1] = test
		else:
			return

def swap_upward(W, i):
	j = (i + 1) // 2 - 1
	if j >= 0 and W[j][1] > W[i][1]:
		test = W[j]
		W[j] = W[i]
		W[i] = test
		swap_upward(W, j)

def update(W, E, a):
	A = []
	for e in E:
		if e[0] != a:
			continue
		else:
			index_2 = e[1]
			for j in range(len(W)):
				if W[j][0] != index_2:
					continue
				elif W[j][1] > e[2]:
					W[j][1] = e[2]
					W[j][2] = e[0]
					A.append(j)
	return A
(n, m) = input().split()
(n, m) = (int(n), int(m))
E = []
for i in range(m):
	(a, b, w) = input().split()
	(a, b, w) = (int(a), int(b), int(w))
	E.append((a, b, w))
	E.append((b, a, w))
s = int(input())
W = []
inf = float('inf')
for i in range(n):
	W.append([i + 1, inf, -1])
for i in range(n // 2, -1, -1):
	heapify(W, i)
W[s - 1][1] = 0
temp = W[s - 1]
W[s - 1] = W[0]
W[0] = temp
sum_weight = 0
while len(W) != 0:
	A = []
	a = W[0][0]
	test = W[0][1]
	sum_weight += test
	W[0] = W[len(W) - 1]
	W.pop()
	heapify(W, 0)
	A = update(W, E, a)
	if len(A) != 0:
		for i in range(len(A)):
			swap_upward(W, A[i])
print(sum_weight)


parent = dict()
rank = dict()

def make_set(vertice):
	parent[vertice] = vertice
	rank[vertice] = 0

def find(vertice):
	if parent[vertice] != vertice:
		parent[vertice] = find(parent[vertice])
	return parent[vertice]

def union(vertice1, vertice2):
	root1 = find(vertice1)
	root2 = find(vertice2)
	if root1 != root2:
		if rank[root1] > rank[root2]:
			parent[root2] = root1
		else:
			parent[root1] = root2
			if rank[root1] == rank[root2]:
				rank[root2] += 1
(k, n) = map(int, input().split())
a = []
vertices = set()
for _ in range(n):
	(x, y, r) = map(int, input().split())
	a += [[r, x, y]]
s = int(input())
w = 0
a.sort()
for i in range(n):
	make_set(a[i][1])
	make_set(a[i][2])
for i in range(n):
	if find(a[i][1]) != find(a[i][2]):
		union(a[i][1], a[i][2])
		w += a[i][0]
print(w)


from queue import PriorityQueue
(n, m) = [int(x) for x in input().split()]
nodes = [[] for _ in range(n)]
for _ in range(m):
	(x, y, r) = [int(x) for x in input().split()]
	x = x - 1
	y = y - 1
	nodes[x].append((y, r))
	nodes[y].append((x, r))

def calc_mst(nodes):
	node_amount = len(nodes)
	visited = [False for _ in range(node_amount)]
	candidates = PriorityQueue()
	cost = 0
	node = 0
	candidates.put((node, cost))
	while not candidates.empty():
		(weight, node) = candidates.get()
		if visited[node]:
			continue
		neighbours = nodes[node]
		for (n, r) in neighbours:
			if not visited[n]:
				candidates.put((r, n))
		cost += weight
		visited[node] = True
	return cost
print(calc_mst(nodes))


def create_adj_list(adj, edges, n):
	for edge in edges:
		if edge[1] in adj[edge[0]]:
			if edge[2] >= adj[edge[0]][edge[1]]:
				continue
		adj[edge[0]][edge[1]] = edge[2]
		adj[edge[1]][edge[0]] = edge[2]
MAX = float('inf')

def find_closest_node(mst_set, keys, n):
	min_key = MAX
	for i in range(1, n + 1):
		if mst_set[i] == 0 and keys[i] < min_key:
			min_key = keys[i]
			min_node = i
	return min_node

def prims(n, m, edges, start):
	adj = [{} for i in range(n + 1)]
	create_adj_list(adj, edges, n)
	mst_set = [0 for i in range(n + 1)]
	keys = [MAX for i in range(n + 1)]
	keys[start] = 0
	edge_sum = 0
	for i in range(1, n + 1):
		min_node = find_closest_node(mst_set, keys, n)
		mst_set[min_node] = 1
		edge_sum += keys[min_node]
		for neighbor in adj[min_node]:
			if mst_set[neighbor] == 0 and adj[min_node][neighbor] < keys[neighbor]:
				keys[neighbor] = adj[min_node][neighbor]
	return edge_sum
(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(x, y, r) = map(int, input().split())
	edges.append([x, y, r])
start = int(input())
print(prims(n, m, edges, start))


from heapq import heappush, heappop

def prim(s, G, E):
	res = 0
	queue = [(0, s)]
	seen = set()
	while queue:
		(w, u) = heappop(queue)
		if u in seen:
			continue
		res += w
		seen.add(u)
		for v in G[u]:
			heappush(queue, (E[u, v], v))
	return res
(N, M) = map(int, input().split())
G = {k: [] for k in range(1, N + 1)}
E = {}
for _ in range(M):
	(u, v, w) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
	E[u, v] = min(E.get((u, v), 10 ** 10), w)
	E[v, u] = E[u, v]
S = int(input())
W = prim(S, G, E)
print(W)


from collections import defaultdict
from collections import namedtuple

class Graph:

	def __init__(self):
		self.nodes = defaultdict(set)

	def add(self, nodea, nodeb, weight):
		self.nodes[nodea].add((nodeb, weight))
		self.nodes[nodeb].add((nodea, weight))
graph = Graph()
(nodes, edges) = (int(x) for x in input().split())
for num_edges in range(edges):
	(nodea, nodeb, weight) = (int(x) for x in input().split())
	graph.add(nodea, nodeb, weight)
start = int(input())
visited_nodes = set()
visited_nodes.add(start)
weight = 0
to_check = graph.nodes[start]
while len(visited_nodes) < nodes:
	l = 100001
	next = None
	for pair in to_check:
		if pair[1] < l and pair[0] not in visited_nodes:
			l = pair[1]
			next = pair
	to_check.remove(next)
	visited_nodes.add(next[0])
	weight += next[1]
	to_check = to_check.union(graph.nodes[next[0]])
print(weight)


import sys
from queue import PriorityQueue

class Graph:

	def __init__(self):
		self.vertices = dict()

	def add_edge(self, source, destination, weight):
		if source not in self.vertices:
			self.vertices[source] = Vertex(source)
		if destination not in self.vertices:
			self.vertices[destination] = Vertex(destination)
		self.vertices[source].adj_list.append(Edge(self.vertices[source], self.vertices[destination], weight))
		self.vertices[destination].adj_list.append(Edge(self.vertices[destination], self.vertices[source], weight))

class Vertex:

	def __init__(self, name):
		self.name = name
		self.adj_list = list()

	def __repr__(self):
		return '%s' % self.name

class Edge:

	def __init__(self, source, destination, weight):
		(self.source, self.destination, self.weight) = (source, destination, weight)

	def __repr__(self):
		return '%d %d %d ' % (self.source, self.destination, self.weight)

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

def main():
	(n, m) = [int(x) for x in input().split()]
	(completed, total_cost) = (set(), 0)
	pq = PriorityQueue()
	graph = Graph()
	for m in range(m):
		(source, destination, weight) = [int(x) for x in input().split()]
		graph.add_edge(source, destination, weight)
	start = int(input())
	for ed in graph.vertices[start].adj_list:
		pq.put(ed)
	while not pq.empty():
		current = pq.get()
		ln = len(completed)
		if current.source not in completed:
			completed.add(current.source)
			for ed in current.source.adj_list:
				pq.put(ed)
		if current.destination not in completed:
			completed.add(current.destination)
			for ed in current.destination.adj_list:
				pq.put(ed)
		if len(completed) != ln:
			total_cost += current.weight
	print(total_cost)
main()


import queue
from operator import itemgetter
(nodes, edges) = [int(x) for x in input().split()]
e = []
nodes = [False] + [False for i in range(1, nodes + 1)]
for i in range(edges):
	a = [int(x) for x in input().split()]
	a.reverse()
	e.append(a)
cn = int(input())
nodes[cn] = True
q = queue.PriorityQueue()
ans = 0
while True:
	sl = [x for x in e if x[2] == cn or x[1] == cn]
	e = [x for x in e if x[2] != cn and x[1] != cn]
	for i in sl:
		q.put(i)
	if q.qsize() == 0:
		break
	while q.qsize() > 0:
		n = q.get()
		if nodes[n[2]] == False:
			cn = n[2]
			nodes[n[2]] = True
			ans += n[0]
			break
		elif nodes[n[1]] == False:
			cn = n[1]
			nodes[n[1]] = True
			ans += n[0]
			break
print(ans)


from heapq import *

class Node:

	def __init__(self, node_id):
		self.node = node_id
		self.estimate = 100000 + 1
		self.parent = None
		self.adj_list = []

	def __lt__(self, other):
		return self.estimate <= other.estimate

	def add_adj_node(self, weight):
		self.adj_list.append(weight)

def relax(node1, node2, weight):
	if node2.estimate > weight:
		node2.estimate = weight

def prim(graph, source):
	source.estimate = 0
	tree_nodes = []
	original_list = list(graph)
	heapify(graph)
	total_sum = 0
	while len(graph) != 0:
		temp = heappop(graph)
		tree_nodes.append(temp)
		for i in range(len(temp.adj_list)):
			(adj_node, weight) = temp.adj_list[i].split(' ')
			relax(temp, original_list[int(adj_node) - 1], int(weight))
		heapify(graph)
		total_sum += temp.estimate
	print(total_sum)
T = 1
for i in range(T):
	(N, E) = input().split(' ')
	graph = []
	for i in range(1, int(N) + 1):
		graph.append(Node(i))
	for i in range(int(E)):
		(node1, node2, weight) = input().split(' ')
		graph[int(node1) - 1].add_adj_node(node2 + ' ' + weight)
		graph[int(node2) - 1].add_adj_node(node1 + ' ' + weight)
	prim(graph, graph[int(input()) - 1])


from heapq import heappush, heappop

def prim_minimum_spanning_tree(graph, edges, S):
	seen = set()
	full_set = set(range(1, len(graph) + 1))
	queue = [(0, S)]
	total_weight = 0
	while seen != full_set:
		(e, u) = heappop(queue)
		if u in seen:
			continue
		seen.add(u)
		total_weight += e
		for node in graph[u]:
			edge = edges[u, node]
			heappush(queue, (edge, node))
	return total_weight
(N, M) = map(int, input().split())
graph = {k: [] for k in range(1, N + 1)}
edges = {}
for _ in range(M):
	(x, y, r) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
	edges[x, y] = min(edges.get((x, y), 10 ** 10), r)
	edges[y, x] = edges[x, y]
S = int(input())
res = prim_minimum_spanning_tree(graph, edges, S)
print(res)


def minKey(key, mstSet, N):
	minimum = 10 ** 5 + 1
	u = -1
	for v in range(N):
		if mstSet[v] == False and key[v] < minimum:
			minimum = key[v]
			u = v
	return u

def prims(graph, parent, key, mstSet, N):
	key[0] = 0
	parent[0] = -1
	for i in range(N):
		u = minKey(key, mstSet, N)
		mstSet[u] = True
		for v in range(N):
			if graph[u][v] > -1 and mstSet[v] == False and (graph[u][v] < key[v]):
				parent[v] = u
				key[v] = graph[u][v]
(N, M) = input().split()
N = int(N)
M = int(M)
graph = []
parent = []
key = []
mstSet = []
for i in range(N):
	graph.append([-1] * N)
	parent.append(-N)
	key.append(10 ** 5 + 1)
	mstSet.append(False)
for a0 in range(M):
	(x, y, w) = input().split()
	graph[int(x) - 1][int(y) - 1] = int(w)
	graph[int(y) - 1][int(x) - 1] = int(w)
prims(graph, parent, key, mstSet, N)
MST = 0
for i in range(1, N):
	MST += graph[i][parent[i]]
print(sum(key))


(N, E) = map(int, input().split())
edges = [[] for i in range(N + 1)]
for e in range(E):
	(x, y, r) = map(int, input().split())
	edges[x].append((y, r))
	edges[y].append((x, r))
S = {x + 1 for x in range(N)}
T = set()
E = 0
T.add(S.pop())
while S:
	minStart = -1
	minEnd = -1
	minCost = float('inf')
	for v in T:
		for e in edges[v]:
			if e[0] in S:
				if e[1] < minCost:
					minStart = v
					minEnd = e[0]
					minCost = e[1]
	if minCost < float('inf'):
		E += minCost
		S.remove(minEnd)
		T.add(minEnd)
print(E)


from collections import defaultdict
from heapq import heappush
from heapq import heappop
MAX = 1000000
(N, E) = map(int, input().split())
adj_l = defaultdict(list)
for _ in range(E):
	(x, y, z) = map(int, input().split())
	adj_l[x].append((y, z))
	adj_l[y].append((x, z))
met_set = set()
weights = [MAX] * (N + 1)
s = int(input())
h = []
weights[s] = 0
heappush(h, (0, s))
while h:
	u = heappop(h)
	if u[1] in met_set:
		continue
	met_set.add(u[1])
	for (v, w) in adj_l[u[1]]:
		if w < weights[v] and v not in met_set:
			weights[v] = w
		heappush(h, (w, v))
print(sum(weights[1:]))