외판원 순환 (작은 N)

제한

• $2 \le N \le 10$
• $0 \le D_{i, j} \le 10^6$
• $D_{i, i} = 0$
• $i \ne j$이면 $D_{i, j}$는 0이거나 양수이며, 0이면 그 길은 쓸 수 없다.

입출력 예시

입력 1

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

출력 1

80

설명: 가능한 순환들 중 $0 \to 1 \to 3 \to 2 \to 0$이 $10+25+30+15=80$으로 최소.

입력 2

2
0 5
3 0

출력 2

8

설명: $0 \to 1 \to 0$이 유일하고 비용은 $5+3=8$.

입력 3

3
0 0 1
1 0 0
0 1 0

출력 3

3

설명: $0 \to 2 \to 1 \to 0$가 유일한 순환 (각 비용 1+1+1).