from __future__ import print_function
from sys import stdin

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

MAX_VERTICES = 9        # 최대 정점의 수
MAX_EDGES = 16          # 최대 간선의 수
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      # 방문하지 않는 정점을 위한 변수
    # 0~n의 정점들 중 방문하지 않는 첫 번째 정점 찾음
    for i in range(0, n):
        if not selected[i]:
            v = i
            break
    # 최단 거리를 갖는 정점 v를 찾음
    for i in range(0, n):
    # 만약 정점 i를 방문하지 않고 정점 i까지의 최단 거리가 정점 v까지의 최단 거리보다 작으면
        if (not selected[i]) and (dists.dist[i] < dists.dist[v]):
            v = i       # 최단 거리를 갖는 정점 v를 갱신
    return v            # 최단 거리를 갖는 정점 v를 반환

# 시작 정점 s부터 나머지 모든 정점들까지의 최단 거리를 계산하는 함수
def prim(s, n):
    printf("  \t\t\t")
    # 최단 거리를 갖는 dists.dist와 정점 방문에 대한 배열을 초기화
    for u in range(0, n):
        dists.dist[u] = INF
        selected[u] = False
    
    # 시작 정점에 대한 최단 거리를 0으로 선언
    dists.dist[s] = 0
   
    for i in range(0, n):
        u=get_min_vertex(n)        # 최단 거리를 갖고 아직 방문하지 않는 정점
        selected[u] = True         # 정점 u를 방문했다고 표시
        # 정의에 따라 연결되지 않는 정점이 있을 경우 최소 스패닝 트리를 찾을 수 없음
        if dists.dist[u] == INF:
            return
        # 시작 정점부터 최단 거리를 갖는 정점과 인접한 정점 사이의 간선을 출력 
        if u != s:
            printf("(%c, %c) "%(dists.edge[u][0], dists.edge[u][1]))
        
        # 정점 u를 거쳐서 아직 방문하지 않는 정점 v까지 오는 경로의 거리가 dists.dist[v]보다 작으면
        # dists.dist[v]를 갱신하는 반복문
        for v in range(0, n):
            if weight[u][v] != INF:
                # 방문하지 않은 정점 v에 대해
                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)

# 가중치 2차원 배열을 초기화
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

# 해당 프로그램에 대한 안내를 출력
print("\n\t\t    \u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510")
print("\t\t    \u2502    가중치 그래프에서 프림 알고리즘으로 최소 스패닝 트리를 찾는 프로그램     \u2502")
print("\t\t    \u2502       (입력될 그래프가 정점 %3d"%MAX_VERTICES,"개와 간선 %3d"%MAX_EDGES,"개를 포함해야 함)       \u2502")
print("\t\t    \u2502 (입력될 그래프의 정점의 수와 간선의 수를 코드에서 변경할 수 있음) \u2502")
print("\t\t    \u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518\n")

printf("\t\t     [정점_1 정점_2 가중치]를 다음 형태대로 (정점을 영어 알파벳 소문자로) 입력하라.\n")
printf("\t\t     예제: a b 10")
list = []      # 입력으로 들어올 간선과 가중치를 저장하기 위한 2차원 배열 선언
start = 0      # 처음으로 입력될 시작 정점의 ASCII 코드를 저장하는 변수
# MAX_EDGES개의 간선을 사용자로부터 입력받음
for i in range(0, MAX_EDGES):
    printf("\n\t\t\t      \u00B7")
    list += stdin.readline().strip('\n').split()  # 입력된 문자열을 추가로 대입
    u_temp = ord(list.pop(0))  # 방금 입력된 간선의 첫 번째 정점의 ASCII 코드
    v_temp = ord(list.pop(0))  # 방금 입력된 간선의 두 번째 정점의 ASCII 코드
    temp = int(list.pop(0))    # 방금 입력된 간선의 가중치 대입
    if i == 0:                 # 맨 처음에 입력된 시작 정점
        start = u_temp - 97
    u = u_temp - 97
    v = v_temp - 97
    weight[u][v] = temp        # u-v 간선의 가중치 대입
    weight[v][u] = temp        # v-u 간선의 가중치 대입
 
printf("\n\t\t\t그러므로 %c로부터 최소 스패닝 트리는 다음과 같다.\n"%chr(start + 65))
prim(start,MAX_VERTICES)       # 최소 스패닝 트리를 계산하는 prim 함수 호출
print("\n\n")

stdin.readline()
