#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 10010
#define M 30100
#define INF 0x3f3f3f3f
struct arr{
	int ff,tt,ww,next;
}c[M];
int X[N],Y[N],Z[N];
struct SEGMENTTREE{
	int l,r,dat;
}t[N << 2];
int n,T;
int r[N];
int root = 0;
int tot = 0;
int fa[N],d[N],top[N],p[N],size[N],son[N];
inline void add(int x,int y){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].next = r[x];
	r[x] = tot;
	return;
}

void build(int p, int l, int r){
	t[p].l = l,t[p].r = r;
	if (l == r){
		t[p].dat = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1,l,mid);
	build((p << 1) + 1,mid + 1,r);
	return;
}

void dfs(int x){
	for (int i = r[x]; i; i = c[i].next){
		int y = c[i].tt;
		if (!d[y]){
			d[y] = d[x] + 1;
			fa[y] = x;
			dfs(y);
			size[y]++;
			size[x] += size[y];
			if (size[son[x]] < size[y]) son[x] = y;
		}
	}
	return;
}
int s = 0;
void dfs1(int x,int y){
	p[x] = ++ s;
	top[x] = y;
	if (son[x]) dfs1(son[x],y);
	else return;
	for (int i = r[x]; i; i = c[i].next){
		int y = c[i].tt;
		if (d[y] == d[x] + 1 && y != son[x]){
			dfs1(y,y);
		}
	}
	return;
}


void change(int p,int x,int y){
	if (t[p].l == t[p].r){
		t[p].dat = y;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (x <= mid) change(p << 1,x,y);
	else change((p << 1) + 1,x,y);
	t[p].dat = max(t[p << 1].dat,t[(p << 1) + 1].dat);
	return;
}


int ask_max(int p,int l,int r){
	if (t[p].l >= l && t[p].r <= r){
		return t[p].dat;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	int ans = -INF;
	if (l <= mid) ans = max(ans,ask_max(p << 1,l,r));
	if (r > mid) ans = max(ans,ask_max((p << 1) + 1,l,r));
	return ans;
}

int ask(int x,int y){
	int fx = top[x],fy = top[y];
	int ans = -INF;
	while (fx != fy){
		if (d[fx] < d[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		ans = max(ans,ask_max(1,p[fx],p[x]));
		x = fa[fx]; fx = top[x];
	}
	if (x == y) return ans;
	if (d[x] > d[y]) swap(x,y);
	ans = max(ans,ask_max(1,p[son[x]],p[y]));
	return ans;
}

void change2(int p,int l,int r){
	if (t[p].l == t[p].r){
		t[p].dat *= -1;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) change2(p << 1,l,r);
	if (r > mid) change2((p << 1) + 1,l,r);
	t[p].dat = max(t[p << 1].dat,t[(p << 1) + 1].dat);
	return;
}

void NEG(int x,int y){
	int fx = top[x],fy = top[y];
	while (fx != fy){
		if (d[fx] < d[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		change2(1,p[fx],p[x]);
		x = fa[fx]; fx = top[x];
	}
	if (x == y) return;
	if (d[x] > d[y]) swap(x,y);
	change2(1,p[son[x]],p[y]);
	return;
}

void clean(){
	memset(son,0,sizeof(son));
	memset(fa,0,sizeof(fa));
	memset(d,0,sizeof(d));
	memset(X,0,sizeof(X));
	memset(Y,0,sizeof(Y));
	memset(Z,0,sizeof(Z));
	memset(p,0,sizeof(p));
	memset(c,0,sizeof(c));
	memset(r,0,sizeof(r));
	memset(t,0,sizeof(t));
	tot = 0;s = 0;
	memset(size,0,sizeof(size));
	memset(top,0,sizeof(top));
}
int main(){
	scanf("%d",&T);
	while (T--){
		clean();
		char cc;
		while (1){
			cc = getchar();
			if (cc == '\r' || cc == '\n') break;
		}
		scanf("%d",&n);
		for (int i = 1; i < n; i++){
			scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
			add(X[i],Y[i]);
			add(Y[i],X[i]);
		}
		root = rand() % n + 1;
		size[root] = 1;d[root] = 1;
		dfs(root);
		dfs1(root,root);
		build(1,1,s);
		for (int i = 1; i < n; i++){
			if (d[X[i]] > d[Y[i]]) swap(X[i],Y[i]);
			change(1,p[Y[i]],Z[i]);
		}
		char ch;
		int x,y;
		while (1){
			while (1){
				ch = getchar();
				if (ch == 'Q' || ch == 'C' || ch == 'N' || ch == 'D') break;
			}
			if (ch == 'D') break;
			switch (ch){
				case 'Q':{
					while (ch != ' ') ch = getchar();
					scanf("%d%d",&x,&y);
					printf("%d\n",ask(x,y));
					break;
				}
				case 'C':{
					while (ch != ' ') ch = getchar();
					scanf("%d%d",&x,&y);
					change(1,p[Y[x]],y);
					break;
				}
				case 'N':{
					while (ch != ' ') ch = getchar();
					scanf("%d%d",&x,&y);
					NEG(x,y);	
					break;
				}
			}
		}
	}
}