Circle

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.

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 the the minimum of the largest number of goods in the rivers.

4
1 3 4
2 4 4
2
1 2 5

4
3

yifenfei

2009浙江大学计算机研考复试（机试部分）——全真模拟