#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define N 10010
#define ls o<<1
#define rs o<<1|1
#define define_m int m=(l+r)>>1
const int INF = ;
int first[N] , k;
struct Edge{
int x , y , next , w;
Edge(){}
Edge(int x , int y , int next , int w):x(x),y(y),next(next),w(w){}
}e[N<<];
void add_edge(int x ,int y , int w)
{
e[k] = Edge(x , y , first[x] , w);
first[x] = k++;
}
int sz[N] , son[N] , dep[N] , fa[N] , num , id[N] , top[N];
void dfs(int u , int f , int d)
{
sz[u] = , fa[u] = f , son[u] = , dep[u] = d;
int maxn = ;
for(int i=first[u] ; ~i ; i=e[i].next){
int v = e[i].y;
if(v == f) continue;
dfs(v , u , d+);
sz[u] += sz[v];
if(maxn<sz[v]) maxn = sz[v] , son[u] = v;
}
}
void dfs1(int u , int f , int head)
{
id[u] = ++num , top[u] = head;
if(son[u]) dfs1(son[u] , u , head);
for(int i=first[u] ; ~i ; i=e[i].next){
int v = e[i].y;
if(v == f || v==son[u]) continue;
dfs1(v , u , v);
}
}
int mx[N<<] , mn[N<<] , neg[N<<] , val[N];
void push_down(int o)
{
if(neg[o]<){
neg[ls]*=neg[o] , neg[rs]*=neg[o];
int tmp;
tmp = mx[ls] , mx[ls] = -mn[ls] , mn[ls] = -tmp;
tmp = mx[rs] , mx[rs] = -mn[rs] , mn[rs] = -tmp;
neg[o] = ;
}
}
void push_up(int o)
{
mx[o] = max(mx[ls] , mx[rs]);
mn[o] = min(mn[ls] , mn[rs]);
}
void build(int o , int l , int r)
{
neg[o] = ;
if(l==r){
mx[o] = mn[o] = val[l];
return ;
}
define_m;
build(ls , l , m);
build(rs , m+ , r);
push_up(o);
}
void change(int o , int l , int r , int p , int v)
{
if(l==r){
mx[o] = mn[o] = v;
return;
}
push_down(o);
define_m;
if(m>=p) change(ls , l , m , p , v);
else change(rs , m+ , r , p , v);
push_up(o);
}
void update(int o , int l , int r , int s , int t)
{
if(l>=s && r<=t){
int tmp;
tmp = mx[o] , mx[o] = -mn[o] , mn[o] = -tmp;
neg[o] *= -;
return ;
}
push_down(o);
define_m;
if(m>=s) update(ls , l , m , s , t);
if(m<t) update(rs , m+ , r , s , t);
push_up(o);
}
int query(int o , int l , int r , int s , int t)
{
if(l>=s && r<=t) return mx[o];
push_down(o);
define_m;
int ans = -INF;
if(m>=s) ans=max(ans , query(ls , l , m , s , t));
if(m<t) ans=max(ans , query(rs , m+ , r , s , t));
return ans;
}
int n , u , v , w;
char str[];
void negatePath(int u , int v)
{
int top1 = top[u] , top2 = top[v];
while(top1!=top2)
{
if(dep[top1]<dep[top2]){
swap(top1 , top2);
swap(u , v);
}
update( , , num , id[top1] , id[u]);
u = fa[top1];
top1 = top[u];
}
if(u!=v){
if(dep[u]<dep[v]) swap(u , v);
update( , , num , id[son[v]] , id[u]);
}
}
int calPath(int u , int v)
{
int top1 = top[u] , top2 = top[v];
int ret = -INF;
while(top1!=top2){
if(dep[top1]<dep[top2]){
swap(top1 , top2);
swap(u , v);
}
ret = max(ret , query( , , num , id[top1] , id[u]));
u = fa[top1];
top1 = top[u];
}
if(u!=v){
if(dep[u]<dep[v]) swap(u , v);
ret = max(ret , query( , , num , id[son[v]] , id[u]));
}
return ret;
}
int main()
{
// freopen("in.txt" , "r" , stdin);
int T;
scanf("%d" , &T);
while(T--)
{
scanf("%d" , &n);
memset(first , - , sizeof(first));
k=;
for(int i= ; i<n- ; i++){
scanf("%d%d%d" , &u ,&v , &w);
add_edge(u , v , w);
add_edge(v , u , w);
}
num = ;
dfs( , , );
dfs1( , , );
for(int i= ; i<n ; i++){
int j=i<< , x=e[j].x , y=e[j].y;
if(fa[x]!=y) val[id[y]] = e[j].w;
else val[id[x]] = e[j].w;
}
build( , , num);
while(scanf("%s" , str)){
if(str[] == 'D') break;
if(str[] == 'C'){
scanf("%d%d" , &u , &v);
u--;
int x = e[u*].x , y = e[u*].y , pos;
if(fa[x]!=y) pos = id[y];
else pos = id[x];
change( , , num , pos , v);
}
else if(str[] == 'N'){
scanf("%d%d" , &u , &v);
negatePath(u , v);
}
else{
scanf("%d%d" , &u , &v);
int ret = calPath(u , v);
printf("%d\n" , ret);
}
}
}
return ;
}
