


import heapq

def 			__SCREAMING_SNAKE_CASE		(		UpperCamelCase		:      Any     ,					UpperCamelCase		:      Union[str, Any]     ,					UpperCamelCase		:      Union[str, Any]	)     ->	List[str]:



	"""simple docstring"""






	a_     			=   [(0, start)]  # cost from start node,end node
	a_     			=   set()
	while heap:
		((a_)			, (a_))     			=   heapq.heappop(UpperCamelCase	)
		if u in visited:
			continue
		visited.add(UpperCamelCase	)
		if u == end:
			return cost
		for v, c in graph[u]:
			if v in visited:
				continue
			a_     			=   cost + c
			heapq.heappush(UpperCamelCase     ,					(next_item, v)	)
	return -1


_A							     =       {
    'A': [['B', 2], ['C', 5]],
    'B': [['A', 2], ['D', 3], ['E', 1], ['F', 1]],
    'C': [['A', 5], ['F', 3]],
    'D': [['B', 3]],
    'E': [['B', 4], ['F', 3]],
    'F': [['C', 3], ['E', 3]],
}
_A							     =       {
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['F', 3]],
    'F': [],
}
_A							     =       {
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}

_A							     =       dijkstra(G, 'E', 'C')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

_A							     =       dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 3 --> F == 3

_A							     =       dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
			import doctest

			doctest.testmod()



def 			__SCREAMING_SNAKE_CASE		(		UpperCamelCase		:      int     ,					UpperCamelCase		:      list[tuple[int, int, int]]	)     ->	list[tuple[int, int, int]]:



	"""simple docstring"""






	a_     			=   sorted(UpperCamelCase     ,					key=lambda UpperCamelCase	: edge[2]	)

	a_     			=   list(range(UpperCamelCase	)	)

	def find_parent(UpperCamelCase		:      Any	):
		if i != parent[i]:
			a_     			=   find_parent(parent[i]	)
		return parent[i]

	a_     			=   0
	a_     			=   []

	for edge in edges:
		a_     			=   find_parent(edge[0]	)
		a_     			=   find_parent(edge[1]	)
		if parent_a != parent_b:
			minimum_spanning_tree_cost += edge[2]
			minimum_spanning_tree.append(UpperCamelCase	)
			a_     			=   parent_b

	return minimum_spanning_tree


if __name__ == "__main__":  # pragma: no cover
			_A     ,				_A							     =       list(map(int, input().strip().split()))
			_A							     =       []

			for _ in range(num_edges):
						_A     ,				_A     ,				_A							     =       (int(x) for x in input().strip().split())
						edges.append((nodea, nodea, cost))

			kruskal(num_nodes, edges)