Без возвращения

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

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

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

Одно число.