from __future__ import print_function
from sys import stdin

def printf(str, *args):
	print(str % args, end='')

MAX_VERTICES = 8
MAX_EDGES = 12
INF = 1000

class Dist:
	def __init__(self):
		self.dist = [0 for i in range(MAX_VERTICES)]
		self.edge = [['' for j in range(2)] for i in range(MAX_VERTICES)]

weight = [[0 for j in range(MAX_VERTICES)] for i in range(MAX_VERTICES)]

selected = [False for j in range(MAX_VERTICES)]
dists = Dist()

def get_min_vertex(n):
	v = -1
	for i in range(0, n):
		if not selected[i]:
			v = i
			break

	for i in range(0, n):
		if (not selected[i]) and (dists.dist[i] < dists.dist[v]):
			v = i
	return v

def prim(s, n):
	for u in range(0, n):
		dists.dist[u] = INF
		selected[u] = False
	dists.dist[s] = 0

	for i in range(0, n):
		u=get_min_vertex(n)
		selected[u] = True
		if dists.dist[u] == INF:
			return
		if u != s:
			printf("(%c, %c) "%(dists.edge[u][0],dists.edge[u][1]))

		for v in range(0, n):
			if weight[u][v] != INF:
				if (not selected[v]) and (weight[u][v] < dists.dist[v]):
					dists.dist[v] = weight[u][v]
					dists.edge[v][0] = chr(65+u)
					dists.edge[v][1] = chr(65+v)

for i in range(0, MAX_VERTICES):
	for j in range(0, MAX_VERTICES):
		if i==j:
			weight[i][j] = 0
		else:
			weight[i][j] = INF
printf("정점의 개수와 간선의 개수를 그래프에 맞게 변경하셨나요\n")
printf("정점_1 정점_2 가중치를 다음 형태대로 입력하세요\n")
printf("예제) a b 10\n\n")
list = []
for i in range(0, MAX_EDGES):
	list += stdin.readline().strip('\n').split()
	u_temp = ord(list.pop(0))
	v_temp = ord(list.pop(0))
	temp = int(list.pop(0))

	u = u_temp - 97;
	v = v_temp - 97;
	weight[u][v] = temp;
	weight[v][u] = temp;


prim(0,MAX_VERTICES)

stdin.readline()