CF24A “環”，圖的遍歷

CF24A “環”，圖的遍歷

 

A. Ring road time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Nowadays the one-way traffic is introduced all over the world in order to improve driving safety and reduce traffic jams. The government of Berland decided to keep up with new trends. Formerly all n cities of Berland were connected by n two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all n roads, but it soon became clear that it's impossible to get from some of the cities to some others. Now for each road is known in which direction the traffic is directed at it, and the cost of redirecting the traffic. What is the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other?

Input

The first line contains integer n (3 ≤ n ≤ 100) — amount of cities (and roads) in Berland. Next n lines contain description of roads. Each road is described by three integers ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — road is directed from city ai to city bi, redirecting the traffic costs ci.

Output

Output single integer — the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.

Sample test(s) input

3
1 3 1
1 2 1
3 2 1

output

1

input

3
1 3 1
1 2 5
3 2 1

output

2

input

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

output

39

input

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

output

0

/**
CF 24A  “環”，圖的遍歷
題目大意:給定n個點和n條有向邊，所有的邊把n個點構成了一個“環”，問如何改變其中一些邊的方向使得從任意一點開始都可以遍歷其他各點。
解題思路：對於每兩個點之間都進行雙向建邊，給定的權值為w，未給定的權值為0，沿一個方向遍歷“環”統計權值和m，答案為min(m,sum-m);
*/
#include 
#include 
#include 
#include 
using namespace std;

int head[105],ip;
int sum,flag[105],n;
void init()
{
    memset(flag,0,sizeof(flag));
    memset(head,-1,sizeof(head));
    ip=0;
    sum=0;
}
struct note
{
    int v,w,next;
}edge[405];

void addedge(int u,int v,int w)
{
    edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++;
}

void dfs(int u,int pre)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre||flag[v])continue;
        sum+=edge[i].w;
        flag[v]=1;
        dfs(v,u);
    }
}

int main()
{
    while(~scanf(%d,&n))
    {
        init();
        int m=0;
        for(int i=0;i