import heapq as hq
import math
INF = float("inf")



print(math.inf, INF)

def prim(G):
    first=True
    firstn=-1
    mayor = 0
    pos =-1
    n = len(G)
    Known = [False]*n
    #FirstTime = [-1]*n
    FirstTime=[]
    Cost = [math.inf]*n
    Path = [-1]*n
    queue = []
    s = 0
    totalDistance=0
    Cost[s] = 0
    hq.heappush(queue, (0, s))
    while len(queue) > 0:
        _, u = hq.heappop(queue)
        if not Known[u]:
            Known[u] = True
            if first and u is not 0:
                firstn=u
                first=False
            for v, w in G[u]:
                #if first:
                    #if mayor< w:
                      #  mayor=w
                    #    pos=v
                if u not in FirstTime:
                    if not Known[v] and w < Cost[v]:
                        Cost[v] = w
                        Path[v] = u
                        hq.heappush(queue, (w, v))
                #if first:
               # Cost[pos] = mayor
              #  Path[pos] = u
              #  first=False
             #   hq.heappush(queue, (mayor, pos))
            FirstTime.append(u)
            for i in range(len(Cost)):
                _,u = queue[i]
                if u is not i:
                    if u not in FirstTime:
                        Cost[i]=math.inf

    u = 0
    menor=1000000
    poss=-1
    print(firstn)
    for v, w in G[u]:
        if v not in Path:
            if w < menor and v is not firstn:
                menor=w
                poss=v
    Cost.append(menor)
    Path.append(poss)
    for i in range(len(Cost)):
        totalDistance=totalDistance+Cost[i]
    print(totalDistance)

    return Path, Cost


#"Kms":3150.5989138486757 ,"recorrido": " JUNIN TUMBES LIMA ICA CUSCO JUNIN",

G = [[(1, 379.4789068684117), (2, 310.1146967131383), (3, 1108.1974979562904), (4, 334.64345985869596)], [(0, 379.4789068684117), (2, 478.2196271563756), (3, 1254.0505590111545), (4, 257.99790461704424)], [(0, 310.1146967131383), (1, 478.2196271563756), (3, 1413.7414626163775), (4, 582.0488193942442)], [(0, 1108.1974979562904), (1, 1254.0505590111545), (2, 1413.7414626163775), (4, 996.0691874058272)], [(0, 334.64345985869596), (1, 257.99790461704424), (2, 582.0488193942442), (3, 996.0691874058272)]]
#with open('grafito.in') as f:
#    for line in f:
#        u = len(G)
#        G.append([])
#        nums = [int(x) for x in line.split(' ')]
#        for i in range(len(nums) // 2):
 #           G[u].append((nums[i * 2], nums[i * 2 + 1]))


for i in range(len(G)):
    stra =''
    for j in range(len(G[i])):
        stra= stra + str(G[i][j])
    print(stra)
print(prim(G))