Under the command "Save Sergeant Ryan," Aiz's rescue team fought fierce battles with enemy forces in the floating city of Lee, Germany. They successfully joined the sergeant, but there were many enemy tanks and they could not call a rescue herio. So, in order to confuse the enemy tanks, they decided to carry out an operation to blow up all the bridges in the city.

The operation was immediately communicated to HQ and preparations for a rescue helicopter were underway. In order to fly the rescue herio, you have to predict when all the bridges will be blown up. As a military programmer, your mission is to calculate the time the rescue team will need to blow up all the bridges.

The floating city is made up of N islands, with a bridge between the islands. All the islands are connected in a tree shape (see the figure below). There is only one route from one island to another. It takes a fixed amount of time to cross each bridge, and it is possible to cross the bridge in either direction at that time.

Rescue units do not have the means to move on the water, such as boats, so the only way to move between islands is through a bridge. Rescue units can instantly blow up the bridges adjacent to the island at that time. What is the minimum time required for a rescue unit to blow up all the bridges? However, we do not consider the travel time within the island.

Create a program that inputs the number of islands and information on each bridge and outputs the minimum time required to blow up all the bridges. Each island is represented by a number from 1 to N. There are N-1 bridges. The bridge information consists of the numbers (a, b) of the two islands adjacent to the bridge and the time t required to cross the bridge. Rescue units shall start on the island with island number 1.

<image>



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format.


N
a1 b1 t1
a2 b2 t2
::
aN-1 bN-1 tN-1


All inputs are given as integers. The number of islands N (2 ≤ N ≤ 20) is given on the first line.

The following N-1 line gives information on the i-th bridge. ai, bi, ti (1 ≤ ti ≤ 500) means that we can move between island ai and island bi in time ti through the i-th bridge.

The number of datasets does not exceed 100.

Output

For each dataset, print the minimum time required to blow up all the bridges on one line.

Example

Input

7
1 2 5
2 3 2
3 4 3
2 5 3
5 6 3
5 7 8
0


Output

12
#include <iostream>
#define MAX 20
#define INF 1000000
using namespace std;

struct Eg{
	int from;
	int to;
	int time;
//	int kind; //1なら親、-1なら子
};

int SB[MAX];//こいつらグローバル
int SG[MAX];

Eg br[MAX];

int counter=0,flag=0;
int ans[1000];

int solve_back(int n,int N){//出発点,Eg本数+1 //メモ化
	if(SB[n]!=INF) return SB[n];
	int X=0;
	bool check=false;
	for(int i=0;i<N-1;i++){
		if(br[i].from==n) { check=true;
			X+=(solve_back(br[i].to,N)+br[i].time*2);
		}
	}
	if(check) {SB[n]=X; return X;}//子を持つとき
	else for(int i=0;i<N-1;i++){
		if(br[i].to==n) {SB[n]=br[i].time*(-2); return SB[n];}
	}
	return 0; 
}

int solve_gone(int n,int N){//出発点,Eg本数+1 //メモ化
	if(SG[n]!=INF) return SG[n];//メモされているとき
	
	
	int count=0;//countは子の数
	for(int i=0;i<N-1;i++){
		if(br[i].from==n) count++;
	}
	
	if(count==0) for(int i=0;i<N-1;i++){
		if(br[i].to==n) {SG[n]=br[i].time*(-1); return SG[n];}//子を持たないとき
	}
	
	
	int min=INF;//子を持つとき
	for(int k=1;k<count+1;k++){
		int ct=k,X=0;
		for(int i=0;i<N-1;i++){
			if(br[i].from==n) {
				ct--;
				if(ct==0) X+=(solve_gone(br[i].to,N)+br[i].time*1);
				else	X+=(solve_back(br[i].to,N)+br[i].time*2);
			}
		}
		if (min>X) min=X;
	}
	SG[n]=min; return SG[n];
}



void solve (){
	int N;
	cin >>N;
	if(N==0) {flag=1; return;}
	//Eg br[MAX];//橋の情報(N-1本しか無い)
	//int F[MAX][MAX]={0};//島ごとの橋の情報管理、0で初期化
	int dis[MAX];//根からの次数
			
	for(int i=0;i<N-1;i++){//入力
		int a,b,t;
		cin >>a>>b>>t;
		br[i].from=--a;//番号をずらす
		br[i].to=--b;
		br[i].time=t;
	//	F[a][b]=F[b][a]=t;
	}
	
	//木として扱いたい,根からの距離必要
	for(int i=1;i<N;i++){
		dis[i]=INF;
	}
	dis[0]=0;//
	while(true){
		bool update=false; //updateあればtrue
		
		for(int j=0;j<N-1;j++){//エッジでまわす
			Eg es=br[j];
			if(dis[es.from]!=INF && 
						dis[es.to]>dis[es.from]+1){
				dis[es.to]=dis[es.from]+1;
				update=true;
			}
		}
		for(int j=0;j<N-1;j++){//エッジでまわす
			Eg es=br[j];
			if(dis[es.to]!=INF && 
						dis[es.from]>dis[es.to]+1){
				dis[es.from]=dis[es.to]+1;
				update=true;
			}
		}
		
		if(!update) break;
	}
	
	for(int j=0;j<N-1;j++){//fromとtoの関係を直す
		if (dis[br[j].from]>dis[br[j].to]){
			int x;
			x=br[j].from; br[j].from=br[j].to; br[j].to=x;
		}
	}
	
	//disは用済み
	for (int i=0;i<MAX;i++){
		SB[i]=SG[i]=INF;
	}
	ans[counter]=solve_gone(0,N);
	counter++;
}
	
	
int main(){
	while(flag==0){
		solve();}
	
	for(int i=0;i<counter;i++)
	cout << ans[i]<<"\n";
}
	