import sys
times: list = []
times.append([0, 830, 937, 834, 718, 750, 1497, 1192, 835])
times.append([992, 0, 1203, 432, 567, 347, 2488, 547, 432])
times.append([1025, 1204, 0, 1157, 592, 1073, 2399, 1585, 1158])
times.append([835, 420, 1153, 0, 517, 117, 2332, 872, 0])
times.append([671, 542, 598, 495, 0, 410, 2168, 923, 495])
times.append([732, 250, 1051, 95, 414, 0, 2229, 770, 96])
times.append([1571, 2168, 2522, 2406, 2289, 2321, 0, 2254, 2406])
times.append([1182, 304, 1556, 736, 920, 651, 2679, 0, 736])
times.append([836, 421, 1154, 1, 518, 118, 2332, 873, 0])
sys.setrecursionlimit(10000)


x: int = 9
stack: list = []
for i in range(x):
    stack.append(0);
road: int = 100000000
final_road: list = []
for i in range(x):
    final_road.append(stack[i])
counter = 1
def min(n: int):
    global counter
    global road
    global x
    if(counter == x):
        tmp = 0
        for i in range(x-1):
            tmp += times[stack[i]][stack[i+1]]
        if tmp < road:
            road = tmp
            for i in range(x):
                final_road[i] = stack[i]
    else:
        for i in range(x):
            tmp1 = 0
            for l in range(counter):
                if i != stack[l]:
                    tmp1 += 1
            if tmp1 == counter:
                stack[counter] = i
                counter += 1
                min(i)
    counter -= 1
min(0)
print(final_road)
print(road)