Problem 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.

4
1 3 4
2 4 4
2
1 2 5

4
3

Author

yifenfei