Circle

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2676
64-bit integer IO format: %I64d      Java class name: Main

Description

There are n citys connecting by rivers. They form a circle as the picture showing.

Half of the citys will send a number of goods to another city by the river, so the other half of city will receive the goods. A city can send the goods by river clockwise or counterclockwise, but the numbers of goods can not change. How to transport let the largest number of goods in the rivers to minimize.
For example n = 4. the city 1 will send 4 goods to the city 3 and the city 2 will send 4 goods to the city 4. Pictures below show the two kinds of methods.

Method 1.
[1->2] = 4 + 2 = 6;
[2->3] = 4 + 2 = 6;
[3->4] = 0 + 2 = 2;
[4->1] = 0 + 2 = 2;
Max = [1->2] = 6;


Method 2.
[1->2] = 2 + 2 = 4;
[2->3] = 2 + 2 = 4;
[3->4] = 2 + 2 = 4;
[4->1] = 2 + 2 = 4;
Max = [1->2] = 4;

So the Method 2 is better than Method 1.

Input

The input contains multiple test cases.
Each case first given a even integer n (2 <= n <= 1000)
Than n/2 lines,each line have three integer A,B,c standing the city A will send c goods to the city B;(1<=A<B<=n, 0<c<=10)

Output

Output the the minimum of the largest number of goods in the rivers.

Sample Input

4
1 3 4
2 4 4
2
1 2 5

Sample Output

4
3

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .