def search_min(tr, vizited):#1 место для оптимизации
    max=-1
    for i in range(len(tr)):
        for j in range(len(tr[i])):
            if tr[i][j]>max:
                max=tr[i][j]
    min=max
    for ind in vizited:
        for index, elem in enumerate(tr[ind]):
            if elem>0 and elem<min and index not in vizited:
                min=elem#веса путей
                index2=index# индекс города
    return [min, index2]

def prim(matr):
    toVisit=[i for i in range(1,len(matr))]# города кроме начального(0)
    vizited=[0]
    result=[0]# начнем с минска
    for index in toVisit:
        weight, ind=search_min(matr, vizited)
        result.append(weight)#в результат будут заноситься веса
        vizited.append(ind)# содержит карту пути
    return result

matr = [
         [1,2,1],
         [2,3,2],
         [3,1,3],
       ]
nm=[]
m=[]
for i in range(len(matr)):
    for j in range(len(matr)):
        m.append(-1)
    nm.append(m)
    m=[]
for i in range(len(nm)):
    for j in range(len(nm[i])):
        if i==j:
            nm[i][j]=0

for st in range(len(matr)):
    i=matr[st][0]-1
    j=matr[st][1]-1
    nm[i][j]=matr[st][2]
    nm[j][i] = matr[st][2]

print(sum(prim(nm)))