#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,cnt,head[10010<<1];
int fa[10010][32],dep[10010];
int lg[10010],t;
ll d[10010];
struct Node{
	int u,to,w;
}Edge[10010<<1];

inline int read(){
	int x=0,k=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*k;
}
inline void add(int x,int y,int z){
	Edge[++cnt].to=y;
	Edge[cnt].u=head[x];
	Edge[cnt].w=z;
	head[x]=cnt;
}
void dfs(int now,int fath){
	dep[now]=dep[fath]+1;
	fa[now][0]=fath;
	for(int i=1;i<=lg[dep[now]];i++)
		fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=Edge[i].u){
		int to=Edge[i].to;
		if(to!=fath){
	//		cout<<now<<"->"<<to<<endl;
			d[to]=d[now]+Edge[i].w;
			dfs(to,now);	
		}
	}
}
inline int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y])
		x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y) return x;
	for(int i=lg[dep[x]]-1;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
void init(){
	memset(Edge,0,sizeof(Edge));
	memset(fa,0,sizeof(fa));
	memset(d,0,sizeof(d));
	memset(dep,0,sizeof(dep));
	memset(head,0,sizeof(head));
}
int main(){
//	freopen("data.txt","r",stdin);
//	freopen("wa.txt","w",stdout);
	t=read();
	for(int i=1;i<=10000;i++)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	while(t--){
		init();
		n=read();
		for(int i=1;i<n;i++){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);add(y,x,z);
		}
		
		dfs(1,0);
//	for(int i=1;i<=n;i++) cout<<dep[i]<<" ";
		char s[10];
		memset(s,0,sizeof(s));
		while(cin>>s&&s[1]!='O'){
			if(s[0]=='D'){
				int x,y;
//				cerr<<"debug"<<endl;
				x=read(),y=read();
				int m=LCA(x,y);
				ll ans=d[x]+d[y]-2*d[m];
				printf("%lld\n",ans);
			}
			if(s[0]=='K'){
				int a,b,k;
				a=read(),b=read(),k=read();
				int m=LCA(a,b);
//				cout<<m<<endl;
				int x=dep[a]-dep[m];
				int y=dep[b]-dep[m];
				if(k==1) printf("%d\n",a);
				else if(k==dep[a]+dep[b]-2*dep[m]+1)
					printf("%d\n",b);
				else if(x>=k-1){
					int e=a;
					for(int i=lg[k]-1;i>=0;i--){
						if(dep[fa[e][i]]>dep[a]-k+1)
							e=fa[e][i];
					}
					printf("%d\n",fa[e][0]);
				}
				else{
					int sum=dep[a]+dep[b]-2*dep[m]+1;
					k=sum-k;
//					cout<<k<<" "<<sum<<endl;
					int e=b;
					for(int i=lg[k]-1;i>=0;i--){
						if(dep[fa[e][i]]>dep[b]-k)
							e=fa[e][i];
					}
					printf("%d\n",fa[e][0]);
				}
			}
		}
	}
	return 0;
}
/*
1
8
1 2 1
1 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
KTH
2 7 5
*/