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

The question needs a very good insight. An important observation is that as the road are equal to the number of nodes that means there are two edges from every node. Now we simply run DFS from any node and visit the neighbouring nodes. For every node we visit we choose two options either enter it or leave it and then reverse the road if necessary If the roads is directed from  A to B then we visit the node B with price 0 therfore leaving+=0 and we enter A from B with a price cost[A][B] which is the cost of reversing the road. The minimum price is minimum of both prices 

*****  code goes here***

#include<iostream>
#include<stdio.h>
#include<list>
#include<vector>
#define ll long long int
using namespace std;
list<int> arr[110];
ll cost[110][110];
bool path[110][110];
int leaving=0,entering=0;
void dfs(int node)

{
// cout<<node<<" "<<entering<<" "<<leaving<<endl;
 list<int> :: iterator it;
 for(it=arr[node].begin();it!=arr[node].end();it++)
 {
 // cout<<"here"<<endl;
  if(path[node][*it]==0)
  {
   if(cost[node][*it]<0)
   {
    entering+=-1*cost[node][*it];
   }
   else
   {
    leaving+=cost[node][*it];
   }
   path[node][*it]=1;
   path[*it][node]=1;
   dfs(*it);
  }
 }
}
int main()
{
 int n;
 cin>>n;
 int a,b,c;
 for(int i=0;i<n;i++)
 {
  cin>>a>>b>>c;
  arr[a].push_back(b);
  arr[b].push_back(a);
  cost[a][b]=c;
  cost[b][a]=-c;
 }
 dfs(1);
 cout<<min(entering,leaving)<<endl;
 return 0;
}

   *** code ends here ***