思路: DFS

题目保证路在无向图上一定是个环，我们要做的就是使得这个图是顺时针的有向图还是逆时针的有向图。

考虑顺时针和逆时针两种情况即可。

时间复杂度：$O(n)$

代码

C++

题目描述

现在有一个城市，城市中有 $n$ 个景点，$n$ 条路，这 $n$ 条路构成了一个环形路，但是每条路都是单向路。

作为这个城市中最有名的工程师，小红被邀请来修路。市长希望修完后的路，可以从任意一个景点 $A$ 到达任意一个景点 $B$ 。

但是，由于城市资金有限，修完后的路依旧只能是单向路，对于第 $i$ 条路，直接连接了景点 $u_i$ 和景点 $v_i$ ，但是需要花费 $w_i$ 的资金。

为了锻炼你的能力，小红想问问你在这种情况下，最少花费多少资金可以使得修完后的路，可以从任意一个景点 $A$ 到达任意一个景点 $B$ 。

输入描述

第一行，一个整数 $n(2\leq n\leq 10^5)$，表示景点个数

接下来 $n$ 行，每行三个整数 $u_i,v_i,w_i$， 表示一条从 $u_i$ 到 $v_i(1\leq u_i,v_i\leq n)$ 的有向道路，修改这条路的方向需要花费 $w_i(1\leq w_i\leq 10^4)$ 的资金，保证每个景点都恰好有两条路。

输出描述

一个整数，表示使得修完后的路，可以从任意一个景点 $A$ 到达任意一个景点 $B$ 的最少资金。

样例

输入

3
1 2 1
3 2 10
3 1 2

输出

3

说明

改变第一条路的方向和第三条路的方向，需要资金为 $3$ 。