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

#define    f               first
#define    s               second
#define    pb              push_back
#define    mp              make_pair
#define    sz              10100

int n;
vector<int> adj[sz+5],vden1[sz+5],vden2[sz+5],costn[sz+5];
int anc[sz+5][15];
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 +5];

int m=0,chaino=0,den=0;
int z=0;
void build(int node,int s,int e) {
    z++;
    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]= tree[2*node]>tree[2*node +1] ? tree[2*node] : tree[2*node +1];
    }
}

void update(int node,int s,int e,int idx,int val) {
    z++;
    if(s==e) {
        tree[node]=val;
        mainarr[idx]=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]= tree[2*node]>tree[2*node +1] ? tree[2*node] : tree[2*node +1];
    }
}

int query(int node,int s,int e,int l,int r) {
    z++;
    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 p1>p2 ? p1 : p2;
}


void dfs1(int cur,int prev) {
    z++;
    int i,j,k;
    anc[cur][0]=prev;
    subtree[cur]=1;
    parent[cur]=prev;
    
    for(i=0;i<adj[cur].size();i++) {
        z++;
        if(adj[cur][i]!=prev) {
            
            level[adj[cur][i]]=level[cur] +1;
            dfs1(adj[cur][i],cur);
            
            subtree[cur]+=subtree[adj[cur][i]];
        }
    }
}

void hld1(int cur,int prev,int cost) {
    z++;
    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++) {
        z++;
        if(adj[cur][i]!=prev) {
            
            if(subtree[adj[cur][i]]>mss || mss==-1) {
                
                mss=subtree[adj[cur][i]];
                vtx=adj[cur][i];
                ec=costn[cur][i];
            }
        }
    }
    
    if(mss!=-1) hld1(vtx,cur,ec);
    
    for(i=0;i<adj[cur].size();i++) {
        z++;
        if(adj[cur][i]!=prev && adj[cur][i]!=vtx) {
            den=0;
            chaino++;
            hld1(adj[cur][i],cur,costn[cur][i]);
        }
    }
}

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

int lca(int x,int y) {
    z++;
    int i,j,k,lg;
    if(level[y]>level[x]) {
        int swap=x;
        x=y;
        y=swap;
    }
    
    int diff=level[x]-level[y];
    for(int i=0;i<14;i++) if((diff>>i)&1) x=anc[x][i];
    if(x==y) return x;
    
    for(i=13;i>=0;i--) {
        z++;
        if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]) {
            x=anc[x][i];
            y=anc[y][i];
            //return parent[x];
        }
    }
    return parent[x];
}

int querybreak(int u,int v) {
    
    z++;
    //if(level[v]>level[u]) swap(u,v); // level of u will always be greater than v
    
    int uchain=vchain[u];
    int vchaino=vchain[v];
    int ans=0,val,mne,mxe;
    while(1) {
        
        if(u==v) break;
        z++;
        uchain=vchain[u];
        //cout<<"uchain="<<uchain<<" "<<vchaino<<"\n";
        if(uchain==vchaino) {  // u at higher level and v at lower level
             
            //  if(level[v]>level[u]) {
            //      int swap=u;
            //      u=v;
            //      v=swap;
            //  }
             if(povinc[v]+1 > povinc[u])
             {
             	mne=povinc[u];
             	mxe=povinc[v]+1;
             }
             else
             {
             	mxe=povinc[u];
             	mne=povinc[v]+1;
             }
             //cout<<"mne="<<mne<<" mxe="<<mxe<<"\n";
             val=query(1,1,m,mne,mxe);
             if(val > ans)
             ans=val;
             break;
        }
        
        //cout<<povinc[u]<<" "<<headofchain[uchain]<<" "<<povinc[headofchain[uchain]]<<"\n";
        if(povinc[u] > povinc[headofchain[uchain]])
        {
        	mne=povinc[headofchain[uchain]];
            mxe=povinc[u];
        }
        else
        {
        	mxe=povinc[headofchain[uchain]];
            mne=povinc[u];
        }
        
        val=query(1,1,m,mne,mxe);
        //ans=maxi(ans,val);
        if(val > ans)
        ans=val;
        u=headofchain[uchain];
        u=parent[u];
    }
    return ans;
}

int _querybreak(int u,int v) {
    
    z++;
    int la=lca(u,v);
    // if(level[v]>level[u]) {
    //     int swap=u;
    //     u=v;
    //     v=swap;
    // }
    
    // cout<<"u="<<u<<" v="<<v<<"\n";
    // cout<<"lca="<<la<<"\n";
    
    int v1=querybreak(u,la);
    //cout<<"\n";
    int v2=querybreak(v,la);
    
    //cout<<"v1="<<v1<<" v2="<<v2<<"\n";
    //return maxi(v1,v2);
    return v1>v2 ? v1 : v2;
}

int main() {
    
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    
    int i,j,k;
    
    int t;
    scanf("%d",&t);
    
    clock_t start=clock();
    while(t--) {
        
        scanf("%d",&n);
        
        chaino=0;m=0;den=0;
        for(i=0;i<=n;i++) {
            z++;
            adj[i].clear();
            costn[i].clear();
            vden1[i].clear();
            vden2[i].clear();
            headofchain[i]=-1;
            for(j=1;j<=14;j++) {
                anc[i][j]=-1;
            }
        }
        int u,v,ec;
        
        for(i=1;i<=(n-1);i++) {
            z++;
            scanf("%d %d %d\n",&u,&v,&ec);
            adj[u].pb(v);
            adj[v].pb(u);
            costn[u].pb(ec);
            costn[v].pb(ec);
            vden1[i].pb(u);
            vden2[i].pb(v);
        }
        level[1]=0;
        dfs1(1,0);
        hld1(1,0,0);
        precompute();
        m=m-1;
        build(1,1,m);
        
        int x,y;
       // cout<<"mainarray"<<endl;
        //for(int i=1;i<=n;i++)
       // {cout<<mainarr[i]<<" ";
       // }
       // cout<<endl;
        while(1) {
            z++;
            char s[10];
            scanf("%s",s);
            if(s[0]=='D') break;
            
            if(s[0]=='Q') {
               scanf("%d %d",&x,&y);
               printf("%d\n",_querybreak(x,y));
            }
            else {
                scanf("%d %d",&x,&y);
                //cout<<"x="<<x<<" y="<<y<<"\n";
                int fn=vden1[x][0],sn=vden2[x][0];
                
                //cout<<fn<<" "<<sn<<"\n";
                if(level[sn]>level[fn]) {
                    
                    int swap=fn;
                    fn=sn;
                    sn=swap;
                }
                //cout<<povinc[fn]<<"\n";
                update(1,1,m,povinc[fn],y);
                //cout<<tree[2]<<"\n";
            }
        }
    }
    //cout<<"total_itern="<<z<<"\n";
    //double dur=(clock()- start)*1.0/(CLOCKS_PER_SEC);
    //cout<<fixed<<dur<<"\n";
    return 0;
}