← 返回题目列表

Codeforces · 24/A

A. 环路

中文机器翻译题面 查看原题

如今,世界各地都引入单向交通,以提高驾驶安全性并减少交通拥堵。贝尔兰政府决定跟上新趋势。以前,贝尔兰的所有 n 个城市都由 n 条环路双向道路连接起来,即。 e.每个城市都直接与另外两个城市相连,并且从每个城市都可以到达任何其他城市。 Berland 政府在所有 n 条道路上引入了单向交通,但很快就发现从某些城市到其他一些城市是不可能的。现在,对于每条道路,我们都知道交通流向哪个方向,以及重新引导交通的成本。政府至少应该花多少钱来改变道路,以便从每个城市都能到达其他城市?

输入

第一行包含整数 n (3 ≤ n ≤ 100) — Berland 的城市(和道路)数量。接下来的 n 行包含道路的描述。每条道路由三个整数 ai、bi、ci 描述(1 ≤ ai、bi ≤ n、ai ≠ bi、1 ≤ ci ≤ 100)——道路从城市 ai 定向到城市 bi,重定向交通成本 ci。

输出

输出单个整数 - 政府应该花在道路改道上的最小金额,以便从每个城市都可以到达任何其他城市。

示例

输入 #1

3
1 3 1
1 2 1
3 2 1

输出 #1

1

输入 #2

3
1 3 1
1 2 5
3 2 1

输出 #2

2

输入 #3

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

输出 #3

39

输入#4

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

输出#4

0