Объехать все города

Есть $n$ городов, между любыми двумя известно расстояние. Курьер выезжает из города 1, должен побывать в каждом ровно один раз и вернуться в первый.

Найдите наименьшую суммарную длину такого маршрута.

В первой строке число $n$ от $2$ до $9$. В следующих $n$ строках по $n$ чисел: расстояния от $1$ до $10^6$. На главной диагонали стоят нули.

Одно число.

Первый город можно закрепить — маршрут от этого не изменится, а перебирать останется $(n-1)!$ порядков вместо $n!$. Для девяти городов это сорок тысяч вариантов.