import numpy as np
Topology = np.mat([[0,175,363,134,216,252,316,189,277,66,103,156,260],
                [175,0,517,55,50,110,396,292,223,128,162,122,394],
                [363,517,0,485,557,517,215,239,320,405,359,416,124],
                [134,55,485,0,94,120,393,288,231,86,121,131,386],
                [216,50,557,94,0,102,437,332,264,168,202,162,434],
                [252,110,517,120,102,0,362,293,205,189,161,123,395],
                [316,396,215,393,437,362,0,128,188,314,279,295,145],
                [189,292,239,288,332,293,128,0,152,209,175,190,97],
                [277,223,320,231,264,205,188,152,0,213,185,131,240],
                [66,128,405,86,168,189,314,209,213,0,40,93,303],
                [103,162,359,121,202,161,279,175,185,40,0,65,257],
                [156,122,416,131,162,123,295,190,131,93,65,0,292],
                [260,394,124,386,434,395,145,97,240,303,257,292,0]])
cities=["南京","无锡","徐州","常州","苏州","南通","连云港","淮安","盐城","镇江","扬州","泰州","宿迁"]
#source,end,value
sev = []
for i in range(Topology.shape[0]):
    for j in range(i+1,Topology.shape[1]):
        item = [i,j,Topology[i,j]]
        sev.append(item)
        
#由小到大排序
def takeThird(elem):
    return elem[2]
sev.sort(key=takeThird)

EndNode = [-1 for i in range(Topology.shape[0])]
#用于判断环
def FindEd(x):
    if EndNode[x] == -1:
        return x
    else:
        return FindEd(EndNode[x])
    
#Kruskal
num = 0
result = 0
New_sev = []
for item in sev:
    snode = FindEd(item[0])
    enode = FindEd(item[1])
    if snode != enode:
        num += 1
        result += item[2]
        EndNode[snode] = enode
        New_sev.append(item)
    if num == Topology.shape[0]-1:
        break
#print(num)
print(result)
#print(New_sev)
for item in New_sev:
    print(cities[item[0]],'--',cities[item[1]],':',item[2])