#include <bits/stdc++.h>

//  M1nK's Ducky Mask: "Strongest Man In The World"

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

#define task "TASK"

#define fi first
#define se second
#define pi acos (-1)
#define pb push_back
#define ll long long
#define ld long double
#define pll pair <ll, ll>
#define pll2 pair <ll, pll>
#define all(a) a.begin (), a.end ()
#define heap_max(a) priority_queue <a>
#define FOR(i, a, b) for (ll i = (a); i <= (b); ++i)
#define FOD(i, a, b) for (ll i = (a); i >= (b); --i)
#define FOr(i, a, b, c) for (ll i = (a); i <= (b); i += (c))
#define FOd(i, a, b, c) for (ll i = (a); i >= (b); i -= (c))
#define heap_min(a) priority_queue <a, vector <a>, greater <a>>

#define Mirai ios_base:: sync_with_stdio (0);
#define Kuriyama cin.tie (nullptr); cout.tie (nullptr);

using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll minN = 1e3 + 7;
const ll maxN = 1e4 + 7;
const ll LOG = __lg (maxN) + 1; 

template <class X> ll getbit (X s, ll i) { return (s >> i) & 1; }
template <class X> ll cntbit (X s) { return __builtin_popcountll (s); }
template <class X, class Y> bool maximize (X &a, Y b) { if (a < b) return a = b, 1; return 0; }
template <class X, class Y> bool minimize (X &a, Y b) { if (a > b) return a = b, 1; return 0; }

// --------------- M1nK_08 --------------- //

string type;
ll t, n, u, v, w;

vector <ll> adj[maxN];
ll a[maxN], val[maxN], edge[maxN];

struct Data { ll x, y, z; } p[maxN];


ll sz[maxN], par[maxN], h[maxN], hv[maxN];
void DFS (ll u, ll p) {
    sz[u] = 1;
    for (auto v: adj[u]) {
        if (v == p) continue;
        par[v] = u;
        h[v] = h[u] + 1;
        DFS (v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[hv[u]]) hv[u] = v;
    }
}

ll st[4 * maxN][2], lz[4 * maxN];
void Lazy (ll id) {
    lz[id] ^= 1;
    ll tmp = st[id][1];
    st[id][1] = -st[id][0];
    st[id][0] = -tmp;
}
void Down (ll id) {
    if (lz[id]) {
        Lazy (id << 1);
        Lazy (id << 1 | 1);
        lz[id] = 0;
    }
}
void Build (ll id, ll l, ll r) {
    if (l == r) {
        st[id][0] = st[id][1] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    Build (id << 1, l, mid);
    Build (id << 1 | 1, mid + 1, r);
    st[id][0] = min (st[id << 1][0], st[id << 1 | 1][0]);
    st[id][1] = max (st[id << 1][1], st[id << 1 | 1][1]);
}
void Upd (ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        st[id][0] = st[id][1] = val;
        return;
    }
    Down (id);
    ll mid = (l + r) >> 1;
    if (pos <= mid) Upd (id << 1, l, mid, pos, val);
    else Upd (id << 1 | 1, mid + 1, r, pos, val);
    st[id][0] = min (st[id << 1][0], st[id << 1 | 1][0]);
    st[id][1] = max (st[id << 1][1], st[id << 1 | 1][1]);
}
ll Get (ll id, ll l, ll r, ll u, ll v) {
    if (r < u || v < l) return -INF;
    if (u <= l && r <= v) return st[id][1];
    Down (id);
    ll mid = (l + r) >> 1;
    return max (Get (id << 1, l, mid, u, v), Get (id << 1 | 1, mid + 1, r, u, v));
}
void Neg (ll id, ll l, ll r, ll u, ll v) {
    if (r < u || v < l) return;
    if (u <= l && r <= v) {
        Lazy (id);
        return;
    }
    Down (id);
    ll mid = (l + r) >> 1;
    Neg (id << 1, l, mid, u, v);
    Neg (id << 1 | 1, mid + 1, r, u, v);
    st[id][0] = min (st[id << 1][0], st[id << 1 | 1][0]);
    st[id][1] = max (st[id << 1][1], st[id << 1 | 1][1]);
}

ll curpos = 1;
ll ID[maxN], pos[maxN];
void HLD (ll u, ll v) {
    ID[u] = v;
    pos[u] = curpos++;
    if (!!hv[u]) HLD (hv[u], v);
    for (auto v: adj[u]) if (v != par[u] && v != hv[u]) HLD (v, v);
}
void UpdPath (ll u, ll v) {
    while (ID[u] != ID[v]) {
        if (h[ID[u]] < h[ID[v]]) swap (u, v);
        Neg (1, 1, n, pos[ID[u]], pos[u]);
        u = par[ID[u]];
    }
    Neg (1, 1, n, min (pos[u], pos[v]) + 1, max (pos[u], pos[v]));
}
ll Query (ll u, ll v) {
    ll ans = -INF;
    while (ID[u] != ID[v]) {
        if (h[ID[u]] < h[ID[v]]) swap (u, v);
        maximize (ans, Get (1, 1, n, pos[ID[u]], pos[u]));
        u = par[ID[u]];
    }
    return max (ans, Get (1, 1, n, min (pos[u], pos[v]) + 1, max (pos[u], pos[v])));
}

void Clear () {
    curpos = 1;
    FOR (i, 1, n) {
        adj[i].clear ();
        p[i] = {0, 0, 0};
        a[i] = val[i] = edge[i] = sz[i] = par[i] = h[i] = hv[i] = ID[i] = pos[i] = 0;
    }
    FOR (id, 0, 4 * maxN) st[id][0] = st[id][1] = lz[id] = 0;
}

void Solve () {
    cin >> t;
    while (t--) {
        cin >> n;
        Clear ();
        FOR (i, 2, n) {
            cin >> u >> v >> w;
            adj[u].pb (v);
            adj[v].pb (u);
            p[i] = {u, v, w};
        }
        DFS (1, -1);
        HLD (1, 1);
        FOR (i, 2, n) {
            u = p[i].x;
            v = p[i].y;
            w = p[i].z;
            if (u == par[v]) edge[i - 1] = v, val[v] = w;
            else edge[i - 1] = u, val[u] = w;
        }
        FOR (i, 1, n) a[pos[i]] = val[i];
        Build (1, 1, n);
        while (cin >> type) {
            if (type == "DONE") break;
            cin >> u >> v;
            if (type == "CHANGE") Upd (1, 1, n, pos[edge[u]], v);
            if (type == "NEGATE") UpdPath (u, v);
            if (type == "QUERY") cout << (u == v ? 0 : Query (u, v)) << '\n';
        }
    }
}

signed main (void) {
    Mirai Kuriyama;
    if (fopen (task".INP", "r")) {
        freopen (task".INP", "r", stdin);
        freopen (task".OUT", "w", stdout);
    } 
    Solve ();
    return 0;
}