import numpy as np

max_size = 20
max_set = (1 << 20)
source = 0
INF = 999999999999

shortest_route = INF
last_position = -1

dist = [[0 for x in range(max_size + 1)] for y in range(max_size + 1)]
result = [[0 for x in range(max_set + 1)] for y in range(max_size + 1)]
previous = [[0 for x in range(max_set + 1)] for y in range(max_size + 1)]
order = []

shops = input()
for i in range(0, int(shops)):
  for j in range(0, int(shops)):
    dist[i][j] = input()

def solve():
  for i in range(1, (1 << shops)):
    for j in range(0, shops):
      if result[i][j] == INF:
        continue

      for k in range(1, shops):
        if (i & ( 1 << k )) != 0:
          continue

        new_pattern = ( i | ( 1 << k ))

        if result[new_pattern][k] > result[i][j] + dist[j][k]:
          result[new_pattern][k] = result[i][j] + dist[j][k]
          previous[new_pattern][k] = j


  for i in range(1, shops):
    if result[ (1 << shops) - 1 ][i] <= 0:
      continue

    if result[ (1 << shops) - 1 ][i] + dist[i][source] < shortest_route:
      shortest_route = result[ (1 << shops) - 1 ][i] + dist[i][source]
      last_position = i

  return shortest_route

def get_order(current, pattern):
  if current == 0:
    return

  order.append(current)
  get_order( previous[pattern][current], new_pattern )
  return

def init():
  for i in range(1, (1 << shops)):
    for j in range(0, shops + 1):
      result[i][j] = INF
      previous[i][j] = j

  result[1][0] = 0
  return



init()
print(solve())
print("\n")

order.append(0)
get_order(last_position, (1 << shops) - 1)
order.append(0)
order.reverse()

for i in range(0, len(order)):
  print(order[i])
  print(" ")