#include<bits/stdc++.h>
using namespace std;

#define    f               first
#define    s               second
#define    ll              int
#define    ld              long double
#define    rd(a)           cin>>a
#define    pt(a)           cout<<a
#define    pb              push_back
#define    mp              make_pair
#define    cl              endl
#define    ifor(i,a,b)     for(i=a;i<=b;i++)
#define    dfor(i,a,b)     for(i=a;i>=b;i--)
#define    pii             pair<int,int>
#define    sz              10100
#define    mad             1000000007

int n;
vector<pair<int,int>> adj[sz+5],vden[sz+5];
int anc[15][sz];
int parent[sz+5],subtree[sz+5];
int mainarr[sz+5];
int vchain[sz+5],povinc[sz+5];
int headofchain[sz+5];
int level[sz+5];
int tree[6*sz];

int m=0,chaino=0,den=0;

void build(int node,int s,int e) {

    if(s==e) {
        tree[node]=mainarr[s];
    }
    else {

        int mid=(s+e)/2;

        build(2*node,s,mid);
        build(2*node +1,mid+1,e);
        tree[node]=max(tree[2*node],tree[2*node +1]);
    }
}

void update(int node,int s,int e,int idx,int val) {

    if(s==e) {
        tree[node]=val;
    }
    else {

        int mid=(s+e)/2;

        if(s<=idx && idx<=mid) {
            update(2*node,s,mid,idx,val);
        }
        else {
            update(2*node +1,mid+1,e,idx,val);
        }
        tree[node]=max(tree[2*node],tree[2*node +1]);
    }
}

int query(int node,int s,int e,int l,int r) {

    if(r<s || e<l) return -1;

    if(s>=l  && e<=r) return tree[node];

    int mid=(s+e)/2;

    int p1=query(2*node,s,mid,l,r);
    int p2=query(2*node +1,mid+1,e,l,r);

    return max(p1,p2);
}
void dfs1(int cur,int prev) {

    int i,j,k;
    anc[0][cur]=prev;
    subtree[cur]=1;
    parent[cur]=prev;

    for(i=0;i<adj[cur].size();i++) {

        if(adj[cur][i].f!=prev) {

            level[adj[cur][i].f]=level[cur] +1;
            dfs1(adj[cur][i].f,cur);

            subtree[cur]+=subtree[adj[cur][i].f];
        }
    }
}

void hld1(int cur,int prev,int cost) {

    int i,j;

    if(den==0) {
        headofchain[chaino]=cur;
        den=1;
    }
    vchain[cur]=chaino;
    povinc[cur]=m;
    mainarr[m++]=cost;

    int mss=-1,vtx,ec;
    for(i=0;i<adj[cur].size();i++) {

        if(adj[cur][i].f!=prev) {

            if(subtree[adj[cur][i].f]>mss || mss==-1) {

                mss=subtree[adj[cur][i].f];
                vtx=adj[cur][i].f;
                ec=adj[cur][i].s;
            }
        }
    }

    if(mss!=-1) hld1(vtx,cur,ec);
    for(i=0;i<adj[cur].size();i++) {

        if(adj[cur][i].f!=prev && adj[cur][i].f!=vtx) {
            den=0;
            chaino++;
            hld1(adj[cur][i].f,cur,adj[cur][i].s);
        }
    }
}

void precompute() {

    int i,j;

    for(i=1;i<=14;i++) {
        for(j=1;j<=n;j++) {
            if(anc[i-1][j]!=-1) {
                anc[i][j]=anc[i-1][anc[i-1][j]];
            }
        }
    }
}

int lca(int x,int y) {

    int i,j,k,lg;
    if(level[y]>level[x]) swap(x,y);

    for(lg=0;1<<lg<=level[x];lg++) {
        lg++;
    }
    lg--;
    for(i=lg;i>=0;i--) {

        if((level[x]-level[y])>=(1<<i)) {
            x=anc[i][x];
        }
    }
    if(x==y) return x;

    for(i=lg;i>=0;i--) {

        if(anc[i][x]!=-1 && anc[i][x]!=anc[i][y]) {
            x=anc[i][x];
            y=anc[i][y];
        }
    }
    return parent[x];
}

int querybreak(int u,int v) {

    if(level[v]>level[u]) swap(u,v);
    int uchain=vchain[u];
    int vchaino=vchain[v];
    int ans=0,val,mne,mxe;

    while(1) {

        if(u==v) break;;

        uchain=vchain[u];
        if(uchain==vchaino) {

             if(level[v]>level[u]) swap(u,v);

             mne=min(povinc[v]+1,povinc[u]);
             mxe=max(povinc[v]+1,povinc[u]);

             val=query(1,1,m,mne,mxe);
             ans=max(ans,val);
             break;
        }

        mne=min(povinc[u],povinc[headofchain[uchain]]);
        mxe=max(povinc[u],povinc[headofchain[uchain]]);

        val=query(1,1,m,mne,mxe);
        ans=max(ans,val);
        u=headofchain[uchain];
        u=parent[u];
    }
    return ans;
}

int _querybreak(int u,int v) {

    int la=lca(u,v);
    if(level[v]>level[u]) swap(u,v);
    int v1=querybreak(u,la);
    int v2=querybreak(v,la);

    return max(v1,v2);
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int i,j,k;

    int t;
    cin>>t;
    while(t--) {

        cin>>n;
        chaino=0;m=0;den=0;
        for(i=0;i<=n;i++) {

            adj[i].clear();
            vden[i].clear();
            headofchain[i]=-1;
        }
        int u,v,ec;

        for(i=1;i<=(n-1);i++) {

            cin>>u>>v>>ec;
            adj[u].pb(mp(v,ec));
            adj[v].pb(mp(u,ec));
            vden[i].pb(mp(u,v));

            for(j=1;j<=14;j++) {
                anc[j][i]=-1;
            }
        }
        level[1]=0;
        dfs1(1,0);
        hld1(1,0,0);
        precompute();
        m=m-1;
        build(1,1,m);

        int x,y;

        while(1) {

            char s[10];
            cin>>s;
            if(s[0]=='D') break;

            if(s[0]=='Q') {
               cin>>x>>y;
               cout<<_querybreak(x,y)<<"\n";
            }
            else {
                cin>>x>>y;
                int fn=vden[x][0].first,sn=vden[x][0].second;
                if(level[sn]>level[fn]) swap(fn,sn);
                update(1,1,m,povinc[fn],y);
            }
        }
    }
    return 0;
}