TSP for SOKOR

import itertools
import math

# distance formula
def distance(x1,y1,x2,y2):
    x1,y1,x2,y2 = float(x1),float(y1),float(x2),float(y2)
    return math.sqrt(((x2-x1)**2)+((y2-y1)**2))

# processing inputs
N = int(input())
inputs = [] # input[i][0] = venue input[i][1] = longtitude in str  input[i][2] = latitude in str
for i in range(N):
    inputs.append(input().split())

# for generating the sequence of indeces
sequences = list(itertools.permutations([i for i in range(1,N)]))
for i in range(len(sequences)):
    sequences[i] = list(sequences[i])
    sequences[i].insert(0,0)

# travel
def travel(seq):
    total_cost = 0
    for i in range(N):
        if i == (N-1):
            total_cost += distance(inputs[seq[i]][1],inputs[seq[i]][2],inputs[0][1],inputs[0][2])*111139
        else:
            total_cost += distance(inputs[seq[i]][1],inputs[seq[i]][2],inputs[seq[i+1]][1],inputs[seq[i+1]][2])*111139
    return total_cost

# finding the sequence with the smallest cost
min = 0
if N <=2 :
    min = travel(sequences[0])
    min_seq = sequences[0]
else:
    for i in range(len(sequences)):
        if i == 0:
            min = travel(sequences[i])
        else:
            temp = travel(sequences[i])
            if temp < min:
                min = temp
                min_seq = sequences[i]

# printing of output
print(round(min,3))
for j in min_seq:
    print(inputs[j][0])