D. Семнадцать стульев

Дана матрица стоимостей проезда между городами. Начав в городе 1, нужно побывать в каждом городе ровно один раз. Найдите наименьшую суммарную стоимость и сам порядок посещения.

Нуль в матрице означает, что дороги нет, а не что проезд бесплатный.

В первой строке $N$ ($1 \le N \le 17$). В каждой из следующих $N$ строк — $N$ неотрицательных чисел $a_{ij}$ ($0 \le a_{ij} \le 100$). Если $a_{ij} > 0$, проезд из $i$ в $j$ стоит $a_{ij}$; если $a_{ij} = 0$, проехать напрямую нельзя.

Если обойти все города можно, в первой строке выведите наименьшую суммарную стоимость, а во второй — $N$ номеров городов в порядке посещения (первый обязан быть 1). Если порядков несколько, выведите любой.

Если обойти все города нельзя, выведите $-1$.