目前，世界各地都引入单向交通（单行道），以提高行车安全，减少交通堵塞。政府决定跟上新趋势。假设该地有n座城市，每座城市都有一个编号，分别为1,2,3,...,n。以前所有的城市都是由n条双向道路连接起来的，即每个城市都直接连接到另外两个城市，而且每个城市都有可以到达其他任何城市。现在政府在所有公路上都引入单向交通，但很快就清楚地表明，从一些城市到其他城市是不可能的。于是政府需要重新规划一些道路的交通方向以解决该问题。现在已知，每条道路的交通方向是什么方向，也知道对该条路进行重新定向的成本。那么政府最少需要花多少钱来重新定向道路，这样以使从每个城市你可以到达其他任何城市吗？

第一行，一个整数n(3<=n<=100) 第2~n+1行，每行三个整数，分别表示该条道路的起点城市编号，终点城市编号，以及对该条道路进行重新定向的成本。

一个整数，表示最少的钱

3
1 3 1
1 2 1
3 2 1

1

迎新赛Div2