#include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define V 100008

 #define E 200008

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define INF 2000000000

 int cnt,n;

 int size[V],dep[V],fa[V],son[V],top[V],w[V],rk[V],a[V];

 struct line{

     int u,v,w,nt;

 }eg[E];

 int lt[V],sum;

 void adt(int u,int v,int w){

     eg[++sum].u=u; eg[sum].v=v; eg[sum].w=w; eg[sum].nt=lt[u]; lt[u]=sum;

 }

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

     adt(u,v,w); adt(v,u,w);

 }

 struct segment_tree{

     // 单点修改 区间取反 区间询问

     int mx[V<<],mn[V<<],lazy[V<<];

     void pushup(int rt){

         mx[rt]=max(mx[rt<<],mx[rt<<|]);

         mn[rt]=min(mn[rt<<],mn[rt<<|]);

     }

     void pushdown(int rt){

         if (lazy[rt]){

             lazy[rt<<]^=;

             lazy[rt<<|]^=;

             int t=mx[rt<<];

             mx[rt<<]=-mn[rt<<];

             mn[rt<<]=-t;

             t=mx[rt<<|];

             mx[rt<<|]=-mn[rt<<|];

             mn[rt<<|]=-t;

             lazy[rt]=;

         }

     }

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

         lazy[rt]=;

         if (l==r){

             mn[rt]=mx[rt]=a[rk[l]];

             return;

         }

         int m=(l+r)/;

         build(lson);

         build(rson);

         pushup(rt);

     }

     void update_1(int x,int val,int l,int r,int rt){

         if (l==r){

             mx[rt]=val;

             mn[rt]=val;

             return;

         }

         pushdown(rt);

         int m=(l+r)/;

         if (x <= m) update_1(x,val,lson);

         if (m <  x) update_1(x,val,rson);

         pushup(rt);

     }

     void  update_2(int L,int R,int l,int r,int rt){

         if (L<=l && r<=R){

             int t=mx[rt];

             mx[rt]=-mn[rt];

             mn[rt]=-t;

             lazy[rt]^=;

             return;

         }

         pushdown(rt);

         int m=(l+r)/;

         if (L <= m) update_2(L,R,lson);

         if (m <  R) update_2(L,R,rson);

         pushup(rt);

     }

     int query(int L,int R,int l,int r,int rt){

         if (L<=l && r<=R){

             return mx[rt];

         }

         pushdown(rt);

         int m=(l+r)/;

         int res=-INF;

         if (L <= m) res=max(res,query(L,R,lson));

         if (m <  R) res=max(res,query(L,R,rson));

         return res;

     }

 }T;

 void dfs_1(int u){

     dep[u]=dep[fa[u]]+; size[u]=; son[u]=;

     for (int i=lt[u];i;i=eg[i].nt){

         int v=eg[i].v;

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

         a[v]=eg[i].w;

         fa[v]=u;

         dfs_1(v);

         size[u]+=size[v];

         if (size[v]>size[son[u]]) son[u]=v;

     }

 }

 void dfs_2(int u,int tp){

     top[u]=tp; w[u]=++cnt; rk[cnt]=u;

     if (son[u]) dfs_2(son[u],tp);

     for (int i=lt[u];i;i=eg[i].nt){

         int v=eg[i].v;

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

         dfs_2(v,v);

     }

 }

 void find_1(int x,int y){

     int res=-INF;

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

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

         res=max(res,T.query(w[top[x]],w[x],,n,));

         x=fa[top[x]];

     }

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

     res=max(res,T.query(w[x]+,w[y],,n,));

     printf("%d\n",res);

 }

 void find_2(int x,int y){

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

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

         T.update_2(w[top[x]],w[x],,n,);

         x=fa[top[x]];

     }

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

     T.update_2(w[x]+,w[y],,n,);

 }

 int main(){

     int tt;

     scanf("%d",&tt);

     while (tt--){

         sum=; cnt=;

         memset(lt,,sizeof(lt));

         scanf("%d",&n);

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

             int u,v,w;

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

             add(u,v,w);

         }

         scanf("\n");

         dfs_1();

         dfs_2(,);

         T.build(,n,);

         char s[];

         for (scanf("%s",s);strcmp(s,"DONE")!=;scanf("%s",s)){

             int x,y;

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

             if (strcmp(s,"QUERY")==){

                 find_1(x,y);

             }

             if (strcmp(s,"CHANGE")==){

                 int u=eg[x*].u , v=eg[x*].v;

                 if (dep[u]<dep[v]) T.update_1(w[v],y,,n,);

                     else T.update_1(w[u],y,,n,);

             }

             if (strcmp(s,"NEGATE")==){

                 find_2(x,y);

             }

         }

     }

 }