严神被隔离久了， 决定出去浪一浪。
严神所在的国家共有n个城市，编号为1 – n. 严神住在1号城市。他想用一个暑假的时间从1号城市出发，不重不漏的走遍所有其他城市最后再回到1号城市。 他知道每两个城市之间都联通并且知道其中火车票的价格。他想知道他的最小花费是多少。
输入共 n + 1 行。
第一行为数字 n , 表示城市个数。
接下来 n 行， 每行 n 个整数。其中第 i 行第 j 个整数代表从城市 i 到城市 j 的火车票价。注意， 因为火车车次的不同，从城市 i 到城市 j 的票价与城市 j 到城市 i 的票价未必相同。
输出一个整数，严神的最小花费。
3 0 1 2 1 0 1 2 1 0
4
对于100%的数据， 2≤n≤20.a_{ii}= 0 .
数据有一定梯度。