import time
from copy import copy


INF = int(1e+100)


def prima(g):
    n = len(g)
    out = []
    for i in range(n):
        out.append([INF] * n)
        out[i][i] = 0

    u = [False] * n
    min_e = [INF] * n
    sel_e = [-1] * n
    min_e[0] = 0
    for i in range(n):
        v = -1
        for j in range(n):
            if not u[j] and (v == -1 or min_e[j] < min_e[v]):
                v = j
        if min_e[v] == INF:
            return False
        u[v] = True

        if sel_e[v] != -1:
            out[v][sel_e[v]] = min_e[v]
            out[sel_e[v]][v] = min_e[v]

        for to in range(n):
            if g[v][to] < min_e[to]:
                min_e[to] = g[v][to]
                sel_e[to] = v
    return out


if __name__ == '__main__':
    print('Привет! Эта программа служит для нахождения остова минимального веса в неориентированном графе, '
          'используя алгоритм Прима.\nЧтобы выйти, введите q на любом этапе\n')

    buffer = ''
    g_count = 0
    e_count = 0
    g = []
    while True:
        buffer = input('Введите количество вершин:\n')
        if buffer.lower() == 'q':
            break
        try:
            g_count = int(buffer)
        except ValueError:
            print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
            continue
        if g_count <= 0:
            print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
            continue
        g = [[INF for j in range(0, g_count)] for i in range(0, g_count)]
        for i in range(g_count):
            g[i][i] = 0

        buffer = input('Введите количество ребер:\n')
        if buffer.lower() == 'q':
            break
        try:
            e_count = int(buffer)
        except ValueError:
            print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
            continue
        if e_count <= 0:
            print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
            continue

        print('Вводите связанные ребра в формате (#1 #2 #weight):')
        flag = False
        for i in range(0, e_count):
            buffer = input()
            if buffer.lower() == 'q':
                break
            a = b = w = -1
            try:
                a, b, w = map(int, buffer.split())
            except ValueError:
                print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
                flag = True
                break
            if a <= 0 or b <= 0 or a > g_count or b > g_count or w < 0:
                print('Вы ввели неверные данные! Пожалуйста, попробуйте снова.\n')
                flag = True
                break
            a -= 1
            b -= 1
            g[a][b] = w
            g[b][a] = w
        if flag:
            continue

        start_time = time.time_ns()
        result = prima(g)
        end_time = time.time_ns()

        if result:
            print('Матрица смежности остова минимального веса данного графа:\n')
            for i in result:
                for j in i:
                    print('INF' if j == INF else str(j), end='\t')
                print('')
        else:
            print('Граф не имеет остова')
        print('Затраченное время - ' + str((end_time - start_time) / 1000000) + 'мс.\n\n')

    print('Спасибо!')


# 1 2 10
# 1 3 5
# 2 3 1
# 2 5 7
# 2 4 25
# 3 4 3
# 3 5 2
# 4 5 1