附代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+10;
int T,n,f[MAXN][30],qzh[MAXN],dep[MAXN],lg[40];
vector<pair<int,int> >G[MAXN];
inline bool id(const char ch){
	return ch>='0'&&ch<='9';
} 
inline int read(void) {
	int s=0;
	char ch=getchar();
	while(!id(ch)) ch=getchar();
	while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void dfs(const int k) {
	for(int i=0;i<G[k].size();i++) {
		if(G[k][i].first!=f[k][0]) {
			f[G[k][i].first][0]=k;
			for(int j=1;j<=20;j++) f[G[k][i].first][j]=f[k][j-1];
			qzh[G[k][i].first]=qzh[k]+G[k][i].second;
			dep[G[k][i].first]=dep[k]+1;
			dfs(G[k][i].first);
		}
	}
	return;
}
inline int cl(int u,int dp) {
	int xl=0;
	while(dp) {
		if(dp&1) u=f[u][xl];
		xl++,dp>>=1;
	}
	return u;
}
inline int lca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	int k=dep[u]-dep[v];
	u=cl(u,k);
	if(u==v) return v;
	for(int i=lg[v];i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return f[u][0];
}
inline void work(void) {
	for(int i=0;i<MAXN;i++) G[i].clear();
	memset(f,0,sizeof(f)),memset(dep,0,sizeof(dep)),memset(qzh,0,sizeof(qzh));
	n=read();
	for(int i=1,a,b,c;i<n;i++)
		a=read(),b=read(),c=read(),G[a].push_back(make_pair(b,c)),G[b].push_back(make_pair(a,c));
	for(int i=0;i<20;i++) f[1][i]=1;
	dep[1]=1;
	dfs(1); 
	string tp;
	int u,v,k;
	while(cin>>tp) {
		if(tp=="DONE") return;
		if(tp=="DIST") {
			u=read(),v=read();
			int lc=lca(u,v);
			printf("%d\n",qzh[u]+qzh[v]-2*qzh[lc]);
		}
		if(tp=="KTH") {
			u=read(),v=read(),k=read();
			int lc=lca(u,v);
			int lcbh=dep[u]-dep[lc]+1;
			if(k<=lcbh) printf("%d\n",cl(u,k-1));
			else printf("%d\n",cl(v,dep[u]+dep[v]-2*dep[lc]+1-k));
		}
	}	
	cout<<'\n';
}
int main() {
	lg[1]=0;
	for(int i=2;i<MAXN;i++) lg[i]=lg[i/2]+1;
	T=read();
	while(T--) work();
	return 0;
}