// LAT Le Anh Tuan
// CEAAURK
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define se second
#define fi first
#define MOD 1000000007
#define MAX 1000000000
using namespace std;

ll n, q, H, timerHLD, t;
ll dep[100005], par[100005];
ll head[100005], heavy[100005], pos[100005], sz[100005];
vector<ll> vec[100005];
struct seg{ll mx, mn, lazy;};
seg tree[200005];
struct Edge{ll u, v, w;};
vector<Edge> canh;

void build(ll u, ll p){
    dep[u]=dep[p]+1;
    par[u]=p;
    sz[u]=1;

    ll mx=0;
    for(auto v:vec[u]){
        if(v==p)continue;
        build(v, u);
        sz[u]+=sz[v];
        if(sz[v]>mx)mx=sz[v], heavy[u]=v;
    }
}

void buildHLD(ll u, ll h){
    head[u]=h;
    pos[u]=++timerHLD;
    if(heavy[u])buildHLD(heavy[u], h);
    for(auto v:vec[u]){
        if(v==par[u] or v==heavy[u])continue;
        buildHLD(v, v);
    }
}

void apply(ll u, ll val){
    auto [mx, mn, lazy]=tree[u];
    if(val%2==1)tree[u].mx=-mn, tree[u].mn=-mx;
    tree[u].lazy+=val;
}

void push(ll u){
    if(u<=n){
        apply(u*2, tree[u].lazy);
        apply(u*2+1, tree[u].lazy);
    }
    tree[u].lazy=0;
}

void Tinh(ll u){for(ll i=H; i>=0; i--)push(u>>i);}

void Tinh2(ll u){
    while(u>1){
        u/=2;
        tree[u].mx=max(tree[u*2].mx, tree[u*2+1].mx);
        tree[u].mn=min(tree[u*2].mn, tree[u*2+1].mn);
    }
}

void update(ll lk, ll rk, ll val){
    lk+=n, rk+=n;
    for(ll l=lk, r=rk; l<=r; l=(l+1)/2, r=(r-1)/2){
        if(l==r)apply(l, val);
        else{
            if(l%2==1)apply(l, val);
            if(r%2==0)apply(r, val);
        }
    }
    Tinh(lk), Tinh(rk);
    Tinh2(lk), Tinh2(rk);
}

void change(ll u, ll v, ll val){
    if(par[v]==u)swap(u, v);
    u=pos[u]+n;//cout<<u<<"\n";
    Tinh(u);
    Tinh2(u);
    tree[u].mx=val, tree[u].mn=val;
    Tinh(u);
    Tinh2(u);
}

ll get(ll l, ll r){
    l+=n, r+=n;
    Tinh(l), Tinh(r);
    ll ans=-MAX;
    for(; l<=r; l=(l+1)/2, r=(r-1)/2){
        if(l==r)ans=max(ans, tree[l].mx);
        else{
            if(l%2==1)ans=max(ans, tree[l].mx);
            if(r%2==0)ans=max(ans, tree[r].mx);
        }
    }
    return ans;
}

ll lcaget(ll u, ll v){
    if(u==v)return 0;
    ll ans=-MAX;
    while(head[u]!=head[v]){
        if(dep[head[u]]<dep[head[v]])swap(u, v);
        ans=max(ans, get(pos[head[u]], pos[u]));
        u=par[head[u]];
    }

    if(dep[u]<dep[v])swap(u, v);
    ans=max(ans, get(pos[v]+1, pos[u]));
    return ans;
}

void lcaupdate(ll u, ll v, ll val){
    while(head[u]!=head[v]){//cout<<u<<" "<<head[u]<<" "<<v<<" "<<head[v]<<"\n";
        if(dep[head[u]]<dep[head[v]])swap(u, v);
        update(pos[head[u]], pos[u], val);
        u=par[head[u]];
    }

    if(dep[u]<dep[v])swap(u, v);
    update(pos[v]+1, pos[u], val);
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);        cout.tie(0);
    if(fopen("Helloworld.inp", "r")){
        freopen("Helloworld.inp", "r", stdin);
        freopen("Helloworld.out", "w", stdout);
    }

    cin>>t;
    while(t--){
        cin>>n;
        for(ll i=1; i<=2*n+1; i++)tree[i]={0, MAX, 0};
        for(ll i=1; i<=n; i++)vec[i].clear();
        for(ll i=1; i<=n; i++)heavy[i]=0;
        canh.clear();
        timerHLD=0;

        H=__lg(n);
        for(ll i=1, u, v, w; i<n; i++){
            cin>>u>>v>>w;
            vec[u].push_back(v);
            vec[v].push_back(u);
            canh.push_back({u, v, w});
        }
        build(1, 0);
        buildHLD(1, 1);
        for(auto [u, v, w]:canh)change(u, v, w);

        string truy;
        for(ll tv=1, i, u, v, val; 1; tv++){
            cin>>truy;
if(truy=="CHANGE")cin>>i>>val, change(canh[i-1].u, canh[i-1].v, val);
            if(truy=="NEGATE")cin>>u>>v, lcaupdate(u, v, 1);
            if(truy=="QUERY")cin>>u>>v, cout<<lcaget(u, v)<<"\n";
            if(truy=="DONE")break;
        }
    }

    return 0;
}