题目描述

解决了庄园的问题后，sxy终于可以放下心来，远离OI，享受人生了。他打算进行一场环球旅行，从家出发，把sxy's home当作第0个景点，途径$N$个世界著名景点。（即算上sxy's home总共有$N+1$个地点）从每个地方都能直接到达另一个地方，需要花费不同的路费。并且由于地方的政策原因，可能从A到B跟从B到A所需的费用还不一样。sxy希望他能从家出发， 走遍所有的这$N$个景点（并且每个景点只能访问一次） 然后回到家（最后要回到家哦），并且花费最小。

输入格式

第一行，一个整数N，即上面描述的N

下面$(N+1)*N$ 行 (也就是说，保证每两个景点之间都有直接一步到达的方案)，每行三个整数，$x,y,c$，表示从$x$地到$y$地需要花费$c$ RMB

输出格式

仅1行，一个整数，sxy完成他的环球旅行所需的最小费用

样例

样例输入

2
0 1 2
0 2 1
1 2 4
1 0 2
2 1 4
2 0 1

样例输出

7

样例解释

最小花费$= 1+4+2 = 7$ $(0->2->1->0)$或$(0->1->2->0)$

数据范围与提示

$1\le N \le 14$

每行输入的$c$满足 $1 \le c \le 1000$