CF24A Ring road

如今，全球范围内都在推广单行道，以提高行车安全并减少交通拥堵。Berland 政府决定跟随这一新趋势。原先 Berland 的所有 $n$ 个城市通过 $n$ 条双向道路组成一个环，也就是说，每个城市正好与另外两个城市直接相连，并且任意城市都能到达其它城市。政府决定将所有 $n$ 条道路改为单向通行，但很快发现，有些城市彼此之间已经无法互通。现在，每条道路的方向以及将该道路反向所需的费用都已知。政府至少需要花多少钱反转路线，才能使任意一对城市都能互达？

第一行包含一个整数 $n$（$3\le n \le 100$），表示 Berland 的城市（及道路）数量。接下来的 $n$ 行描述每条道路，每行包含三个整数 $a_i$、$b_i$、$c_i$（$1\le a_i, b_i\le n$，$a_i\ne b_i$，$1\le c_i\le 100$），表示有一条从城市 $a_i$ 指向城市 $b_i$ 的道路，将这条道路反向的费用为 $c_i$。

输出一个整数，表示为了使任意两城互达，政府需要花费的最少费用。

由 ChatGPT 5 翻译