题目描述

有一个 $n$ 个点和 $n$ 条单向边（没有重边）的图，若将其所有边视为无向的，那么它是连通图。

现在，你可以改变任意一些边的方向。改变 $a_i→b_i$ 这条边的方向（即变为 $b_i→a_i$）需要 $c_i$ 的价格。问最少花多少钱才能使得图连通，从任意点可以到任意点。

输入格式

第一行一个整数 $n$，$3\le n\le 100$。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，$1\le c_i\le 100$。

输出格式

输出一个整数表示答案。

3
1 3 1
1 2 1
3 2 1

1

3
1 3 1
1 2 5
3 2 1

2

6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42

39

4
1 2 9
2 3 8
3 4 7
4 1 5

0