//#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll w=1,c,ret;
    while((c=getchar())> '9'||c< '0')
    w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    ret=ret*10+c-'0';
    return ret*w;
}
int const maxn=1e5+5;
int n,cnt,df;
int h[maxn],sz[maxn],d[maxn],fa[maxn],son[maxn],top[maxn],dfn[maxn];
struct edge{
	int u,v,w;
}E[maxn];
struct node{
	int v,nex;
}e[maxn<<1];
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].nex=h[u];
	h[u]=cnt;
}
//
struct segment{
	int mi[maxn<<2],ma[maxn<<2],laz[maxn<<2];
	inline void up(int p){
		mi[p]=min(mi[p<<1],mi[p<<1|1]);
		ma[p]=max(ma[p<<1],ma[p<<1|1]);
	}
	inline void down(int p){
		if(laz[p]){
			mi[p<<1]=-mi[p<<1];
			ma[p<<1]=-ma[p<<1];
			swap(mi[p<<1],ma[p<<1]);
			laz[p<<1]^=1;
			mi[p<<1|1]=-mi[p<<1|1];
			ma[p<<1|1]=-ma[p<<1|1];
			swap(mi[p<<1|1],ma[p<<1|1]);
			laz[p<<1|1]^=1;
			laz[p]=0;
		}
	}
	inline void build(int x,int k,int l=2,int r=n,int p=1){
		if(r<x||l>x) return;
		if(l==r&&l==x){
			laz[p]=0;
			mi[p]=ma[p]=k;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid) build(x,k,l,mid,p<<1);
		if(mid<x) build(x,k,mid+1,r,p<<1|1);
		up(p);
	}
	inline void mdf(int L,int R,int l=2,int r=n,int p=1){
		if(r<L||l>R) return;
		if(l>=L&&r<=R){
			mi[p]=-mi[p];
			ma[p]=-ma[p];
			laz[p]^=1;
			swap(mi[p],ma[p]);
			return;
		}
		int mid=l+r>>1;
		down(p);
		mdf(L,R,l,mid,p<<1);
		mdf(L,R,mid+1,r,p<<1|1);
		up(p);
	}
	inline int query(int L,int R,int l=2,int r=n,int p=1){
		if(r<L||l>R) return -0x3f3f3f3f;
		if(l>=L&&r<=R){
			return ma[p];
		}
		int mid=l+r>>1;
		down(p);
		return max(query(L,R,l,mid,p<<1),query(L,R,mid+1,r,p<<1|1));
	}
	
}t;
//
void dfs1(int u){
	sz[u]=1;
	d[u]=d[fa[u]]+1;
	for(int i=h[u];i;i=e[i].nex){
		int v=e[i].v;
		if(v==fa[u]) continue;
		fa[v]=u;
		dfs1(v);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	dfn[u]=++df;
	//pr[df]=u;
	if(son[u]) dfs2(son[u],t);
	for(int i=h[u];i;i=e[i].nex){
		int v=e[i].v;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
//
int querypath(int u,int v){
	int ans=-0x3f3f3f3f;
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]){
			swap(u,v);
		}
		ans=max(t.query(dfn[top[u]],dfn[u]),ans);
		u=fa[top[u]];
	}
	if(u!=v){
		if(d[u]>d[v]) swap(u,v);
		//cout<<max(t.query(dfn[top[u]],dfn[u]),ans)<<"\n";
		return max(t.query(dfn[u]+1,dfn[v]),ans);
	}
	//cout<<ans<<"\n";
	return ans;
}
void mdfpath(int u,int v){
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]){
			swap(u,v);
		}
		t.mdf(dfn[top[u]],dfn[u]);
		u=fa[top[u]];
	}
	if(u!=v){
		if(d[u]>d[v]) swap(u,v);
		t.mdf(dfn[u]+1,dfn[v]);
	}
}

inline void init(){
	cnt=0;
	df=0;
	memset(h,0,sizeof(h));
	memset(e,0,sizeof(e));
	memset(sz,0,sizeof(sz));
	memset(fa,0,sizeof(fa));
	memset(d,0,sizeof(d));
	memset(son,0,sizeof(son));
	memset(top,0,sizeof(top));
	memset(dfn,0,sizeof(dfn));
	memset(t.mi,0x3f3f3f3f,sizeof(t.mi));
	memset(t.laz,0,sizeof(t.laz));
	memset(t.ma,-0x3f3f3f3f,sizeof(t.ma));
	memset(E,0,sizeof(E));
}

int main(){
	int _;
	_=read();
	while(_--){
		init();
		n=read();
		for(int i=1,u,v,w;i<n;i++){
			E[i].u=u=read(),E[i].v=v=read(),E[i].w=w=read();
			add(u,v);
			add(v,u);
		}
		dfs1(1),dfs2(1,1);
		for(int i=1;i<n;i++){
			if(d[E[i].u]>d[E[i].v]) swap(E[i].u,E[i].v);
			t.build(dfn[E[i].v],E[i].w);
		}
		string s;
		int u,v;
		while(cin>>s){
			if(s=="DONE") break;
			u=read(),v=read();
			if(s=="QUERY"){
				cout<<querypath(u,v)<<"\n";
			}else if(s=="CHANGE"){
				t.build(dfn[E[u].v],v);
			}else if(s=="NEGATE"){
				mdfpath(u,v);
			}
		}
	}
	
	
	
	return 0;
}