#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	int x,y,next;
}a[210000];int len,last[110000]; 
void ins(int x,int y)
{
	len++; a[len].x=x; a[len].y=y;
	a[len].next=last[x];last[x]=len;
}
struct trnode
{
	int lc,rc,l,r,c;
}tr[210000];int trlen;
void bt(int l,int r)
{
	trlen++; int now=trlen;
	tr[now].l=l;tr[now].r=r; tr[now].c=0;
	tr[now].lc=tr[now].rc=-1;
	if(l<r)
	{
		int mid=(l+r)/2;
		tr[now].lc=trlen+1; bt(l,mid);
		tr[now].rc=trlen+1; bt(mid+1,r);
	}
}
int n,fa[110000],dep[110000],son[110000],tot[110000];
void pre_tree_node(int x)
{
	tot[x]=1;son[x]=0;
	for(int k=last[x];k>0;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa[x]) 
		{
            fa[y]=x;         
			dep[y]=dep[x]+1;  			
            pre_tree_node(y); 
			if(tot[son[x]]<tot[y] )  son[x]=y;
           	tot[x]+=tot[y];  
		}	
	}
}
int z,ys[110000],top[110000];
void pre_tree_edge(int x,int tp)
{
	ys[x]=++z;top[x]=tp;
	if(son[x]!=0) pre_tree_edge(son[x],tp);
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=son[x]&&y!=fa[x]) 
			pre_tree_edge(y,y); 
	}
}
int mymax(int x,int y) { return x>y?x:y;}
void change(int now,int p,int c)
{
	if(tr[now].l==tr[now].r) {tr[now].c=c; return ;}
	int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;	
	if(p<=mid) change(lc,p,c);
    else change(rc,p,c);
	tr[now].c=mymax(tr[lc].c,tr[rc].c);
}  
int findmax(int now,int l,int r)
{
	if( l== tr[now].l && tr[now].r==r) return tr[now].c;
	int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
	if(mid+1<=l) return findmax(rc,l,r);  
	else if(r<=mid)return findmax(lc,l,r);  
	else return mymax(findmax(lc,l,mid),findmax(rc,mid+1,r));
} 
void check(int now,int l,int r)
{
	if(tr[now].l==tr[now].r){tr[now].c*=-1;return;}
	int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
	if(l<=mid) check(lc,l,r);
	else check(rc,l,r);
	tr[now].c=mymax(tr[lc].c,tr[rc].c);
}
void gai(int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
    {
		if(dep[fx]<dep[fy])
        {
			swap(fx,fy);
			swap(x,y);
		}
		check(1,ys[fx],ys[x]);
		x=fa[fx];fx=top[x];
	}
	if(x==y) return;
	if(dep[x]>dep[y]) swap(x,y);
	check(1,ys[son[x]],ys[y]);
}
int solve(int x,int y)
{
	int fx=top[x],fy=top[y],ans=0;
	while(fx!=fy)
	{
		if(dep[fx]>dep[fy]) 
        {                                               
            swap(fx,fy);
			swap(x,y);
        }
		ans=mymax(ans,findmax(1,ys[fy],ys[y]));
		y=fa[fy];fy=top[y];
	}
	if(x==y) return ans; 
	else
    {
        if(dep[x]>dep[y]){ swap(x,y); } 
        return mymax(ans,findmax(1,ys[son[x]],ys[y]));
    }
}
struct bian
{
    int x,y,c;
}e[110000]; 
int main()
{
	int tt;
    scanf("%d",&tt);
	while(tt--)
	{
		scanf("%d",&n);
		len=0;memset(last,0,sizeof(last));
		memset(e,0,sizeof(e));
		memset(a,0,sizeof(a));
		memset(tr,0,sizeof(tr));
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c); 
			ins(e[i].x,e[i].y);
			ins(e[i].y,e[i].x);
		}
		memset(fa,0,sizeof(fa));
		memset(dep,0,sizeof(dep));
		memset(tot,0,sizeof(tot));
		memset(son,0,sizeof(son));
		memset(ys,0,sizeof(ys));
		memset(top,0,sizeof(top));
        dep[1]=0;fa[1]=0;pre_tree_node(1);
		z=0;pre_tree_edge(1,1);
		trlen=0; bt(1,z); 
		for(int i=1;i<n;i++) if(dep[e[i].x]>dep[e[i].y]) { int  t=e[i].x;e[i].x=e[i].y;e[i].y=t;}
		for(int i=1;i<n;i++) change(1,ys[e[i].y],e[i].c);
		char ss[15]; int x,y;
		while(scanf("%s",ss)!=EOF)
		{
			if(ss[0]=='D') break;  
			scanf("%d%d",&x,&y);
			if(ss[0]=='Q')   printf("%d\n",solve(x,y)); 
            if(ss[0]=='N')gai(x,y);  
			else  change(1,ys[e[x].y],y); 
		}
    }
	return 0;
}