Задача №112654. Путь почтальона - 3

Почтальон Печкин ежедневно разносит письма и газеты жителям Простоквашино. Деревня большая, люди живут на хуторах. Печкин хочет каждый день обязательно обойти все хутора, посетив каждый из них только по одному разу. Этот маршрут должен начинаться и заканчиваться на почте. В Простоквашино очень много дорог и тропинок, и Печкин хочет выбрать маршрут минимальной длины. Напишите программу, которая поможет Печкину выбрать наилучший (оптимальный) маршрут.

Входные данные

В первой строке вводится количество хуторов N ( 1 ≤ N ≤ 15 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему расположения хуторов. Положительное число в матрице означает расстояние между хуторами, а ноль говорит о том, что прямой дороги нет.

Выходные данные

В первой строке программа должна вывести общую длину оптимального маршрута. Во второй строке выводится сам маршрут (последовательность номеров хуторов), который начинается с 1 и заканчивается на 1 (пункт номер 1 – это почта). Второй номер пункта в записи маршрута должен быть минимальный из возможных.

Примеры
Входные данные
4
0 1 8 4
1 0 2 5
8 2 0 3
4 5 3 0
Выходные данные
10
1 2 3 4 1 
Сдать: для сдачи задач необходимо войти в систему