#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define mod 1000000000

int n;
ll finans;
vector<vector<pair<int, int>>>adj;

void dfs(int src, int par, int number[])
{
	number[src] = 1;
	for(auto it:adj[src])
	{
		if( it.first != par )
		{
			dfs(it.first, src, number);
			number[src] += number[it.first];
			// cout<<it.first<<"	"<<src<<"	"<<number[it.first]<<"	"<<(n-number[it.first])<<endl;

			ll curr = (  min( number[it.first], n-number[it.first] ) * 2ll * it.second );

			finans += curr;
		}
	}
}


int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif


	int t,a,b,c;
	cin>>t;
	ll ans[t];

	for(int tt=0; tt<t; tt++)
	{
		cin>>n;
		adj.clear();
		adj.reserve(n);
		for(int i=0; i<n-1; i++)
		{
			cin>>a;
			cin>>b;
			cin>>c;
			
			a--;
			b--;

			adj[a].push_back(make_pair(b, c));
			adj[b].push_back(make_pair(a, c));

		}

		int number[n];
		memset(number,0,sizeof(number));

		finans = 0;
		dfs(0,-1,number);
		ans[tt] = finans;
		cout<<"case #"<<(tt+1)<<": "<<ans[tt]<<endl;
	}
	// for(int tt=1; tt<=t; tt++)
	// {
	// 	cout<<"case #"<<tt<<": "<<ans[tt-1]<<endl;
	// }
	return 0;
}