Description

某乡有N个村庄(1<N<40),有一个售货员,他要到各个村庄去售货,各个村庄之间的路程S(0<S<10000)是已知的,且A村到B村与B村到A村的路大多不同.为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为1,他不知道选择什么样的路线才能使所走过的路程最短.请你帮他选择一条最短的路.

Input

村庄N和各个村之间的路程(均是整数).

Output

最短的路程.

Sample Input

3
0 2 1
1 0 2
2 1 0

Sample Output

3 

HINT

Source