#include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int cnt,head[N];

 int size[N],fa[N],dep[N],ww[N],son[N],ide[N];

 int top[N],id[N],tot,w[N];

 int t,n;

 char s[];

 struct edge{

     int to,nxt,w,id;

 }e[N*];

 void add(int u,int v,int w,int id){

     cnt++;

     e[cnt].nxt=head[u];

     e[cnt].to=v;

     e[cnt].w=w;

     e[cnt].id=id;

     head[u]=cnt;

 }

 struct tree{

     int l,r,maxx,minn,lazy;

 }tr[N*];

 void update(int now){

     tr[now].maxx=max(tr[now*].maxx,tr[now*+].maxx);

     tr[now].minn=min(tr[now*].minn,tr[now*+].minn);

 }

 void pushdown(int now){

     if(tr[now].lazy==)return;

     int hh=tr[now*].maxx;

     tr[now*].maxx=-tr[now*].minn;

     tr[now*].minn=-hh;

     hh=tr[now*+].maxx;

     tr[now*+].maxx=-tr[now*+].minn;

     tr[now*+].minn=-hh;

     tr[now*].lazy^=;

     tr[now*+].lazy^=;

     tr[now].lazy=;

 }

 void dfs1(int u,int f,int deep){

     size[u]=;

     fa[u]=f;

     dep[u]=deep;

     int maxson=-;

     for(int i=head[u];i;i=e[i].nxt){

         int v=e[i].to;

         if(v==f)continue;

         ww[v]=e[i].w;

         ide[e[i].id]=v;

         dfs1(v,u,deep+);

         size[u]+=size[v];

         if(size[v]>maxson){

             son[u]=v;

             maxson=size[v];

         }

     }

 }

 void dfs2(int u,int tp){

     top[u]=tp;

     id[u]=++tot;

     w[tot]=ww[u];

     if(!son[u])return;

     dfs2(son[u],tp);

     for(int i=head[u];i;i=e[i].nxt){

         int v=e[i].to;

         if(v==fa[u]||v==son[u])continue;

         dfs2(v,v);

     }

 }

 void build(int l,int r,int now){

     tr[now].l=l;tr[now].r=r;

     tr[now].maxx=tr[now].lazy=tr[now].minn=;

     if(l==r){

         tr[now].maxx=tr[now].minn=w[l];

         return;

     }

     int mid=(l+r)>>;

     build(l,mid,now*);

     build(mid+,r,now*+);

     update(now);

 }

 int getmax(int l,int r,int now){

     pushdown(now);

     if(tr[now].l==l&&tr[now].r==r){

         return tr[now].maxx;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     if(l>mid)return getmax(l,r,now*+);

     else if(r<=mid)return getmax(l,r,now*);

     else {

         return max(getmax(l,mid,now*),getmax(mid+,r,now*+));

     }

 }

 void change(int x,int y,int now){

     pushdown(now);

     if(tr[now].l==tr[now].r){

         tr[now].maxx=tr[now].minn=y;

         return;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     if(x>mid)change(x,y,now*+);

     else if(x<=mid)change(x,y,now*);

     update(now);

 }

 void getfan(int l,int r,int now){

     pushdown(now);

     if(tr[now].l==l&&tr[now].r==r){

         tr[now].lazy^=;

         int hh=tr[now].maxx;

         tr[now].maxx=-tr[now].minn;

         tr[now].minn=-hh;

         return;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     if(l>mid)getfan(l,r,now*+);

     else if(r<=mid)getfan(l,r,now*);

     else{

         getfan(l,mid,now*);

         getfan(mid+,r,now*+);

     }

     update(now);

 }

 int getlca(int x,int y){

     while(top[x]!=top[y]){

         if(dep[top[x]]<dep[top[y]])swap(x,y);

         x=fa[top[x]];

     }

     if(dep[x]<dep[y])return x;

     else return y;

 }

 int getmaxl(int x,int y){

     int ans=-;

     while(top[x]!=top[y]){

         if(dep[top[x]]<dep[top[y]])swap(x,y);

         ans=max(ans,getmax(id[top[x]],id[x],));

         x=fa[top[x]];

     }

     if(x==y)return ans;

     if(dep[x]>dep[y])swap(x,y);

     ans=max(ans,getmax(id[x]+,id[y],));

     return ans;

 }

 void getfanl(int x,int y){

     while(top[x]!=top[y]){

         if(dep[top[x]]<dep[top[y]])swap(x,y);

         getfan(id[top[x]],id[x],);

         x=fa[top[x]];

     }

     if(x==y)return;

     if(dep[x]>dep[y])swap(x,y);

     getfan(id[x]+,id[y],);

 }

 int main(){

     scanf("%d",&t);

     for(int z=;z<=t;z++){

         scanf("%d",&n);

         memset(head,,sizeof(head));

         memset(son,,sizeof(son));

         memset(dep,,sizeof(dep));

         memset(fa,,sizeof(fa));

         memset(size,,sizeof(size));

         memset(ide,,sizeof(ide));

         memset(w,,sizeof(w));

         memset(ww,,sizeof(ww));

         memset(id,,sizeof(id));

         memset(top,,sizeof(top));

         tot=;

         cnt=;

         for(int i=;i<=n-;i++){

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             add(u,v,w,i);

             add(v,u,w,i);

         }

         dfs1(,,);

         dfs2(,);

         build(,n,);

         while(scanf("%s",&s)!=EOF){

             if(s[]=='D')break;

             if(s[]=='Q'){

                 int x,y;

                 scanf("%d%d",&x,&y);

                 int LCA=getlca(x,y);

                 printf("%d\n",max(getmaxl(LCA,x),getmaxl(LCA,y)));

             }

             else if(s[]=='C'){

                 int x,y;

                 scanf("%d%d",&x,&y);

                 change(id[ide[x]],y,);

             }

             else if(s[]=='N'){

                 int x,y;

                 scanf("%d%d",&x,&y);

                 int LCA=getlca(x,y);

                 getfanl(LCA,x);

                 getfanl(LCA,y);

             }

         }

     }

     return ;

 }