如今,世界各地都引入单向交通,以提高驾驶安全性并减少交通拥堵。贝尔兰政府决定跟上新趋势。以前,贝尔兰的所有 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