#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstring>#include <stack>#include <cctype>#include <queue>#include <string>#include <vector>#include <set>#include <map>#include <climits>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 10050#define maxn 30010typedef pair<int,int> PII;typedef long long LL;LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}    return x*f;}int n,m,k,head[N],hcnt,rt;char str[11];struct Node{    int to,nxt,v;}node[maxn];struct Edge{    int x,y,v;}edge[maxn];int seg[N<<2];int siz[N];  ///当前节点保存的儿子数int top[N];  ///当前节点所在链的顶端节点int son[N];  ///保存重儿子int dep[N];  ///当前节点深度int fa[N];   ///当前节点的父亲int id[N];   ///用来保存树中每个节点剖分后的新编号int posi[N]; ///在线段树中的位置int tid,pos;///树链剖分void dfs1(int u,int f,int deep){ ///找重边    dep[u]=deep;    fa[u]=f;    siz[u]=1;    for(int i=head[u];~i;i=node[i].nxt){        int e=node[i].to;        if(e==f)continue;        dfs1(e,u,deep+1);        siz[u]+=siz[e];        if(!son[u]||siz[son[u]]<siz[e])            son[u]=e;    }}void dfs2(int u,int tp){   ///连重边成重链    top[u]=tp;    id[u]=++tid;    posi[id[u]]=u;    if(!son[u])return;    dfs2(son[u],tp);    for(int i=head[u];~i;i=node[i].nxt){        int e=node[i].to;        if(e!=son[u]&&e!=fa[u])            dfs2(e,e);    }}///线段树void build(int rt,int l,int r){    seg[rt]=-inf;    if(l==r) return;    int mid=l+r>>1;    build(lson); build(rson);    seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);}void add(int rt,int l,int r,int v){    if(l==r){        seg[rt]=v;        return;    }    int mid=l+r>>1;    if(pos<=mid)add(lson,v);    else add(rson,v);    seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);}int query(int rt,int l,int r,int L,int R){    if(L<=l&&r<=R){return seg[rt];}    int mid=l+r>>1;    int temp=INT_MIN;    if(L<=mid)temp=max(temp,query(lson,L,R));    if(R>mid) temp=max(temp,query(rson,L,R));    return temp;}void ini(){    mst(head,-1);hcnt=tid=0;mst(seg,0);    mst(son,0);mst(siz,0);}void add(int x,int y,int v){    node[hcnt].to=y,node[hcnt].nxt=head[x],node[hcnt].v=v,head[x]=hcnt++;    node[hcnt].to=x,node[hcnt].nxt=head[y],node[hcnt].v=v,head[y]=hcnt++;}int lca(int x,int y){    int ans=-inf;    while(top[x]!=top[y]){        if(dep[top[x]]<dep[top[y]])swap(x,y);        ans=max(ans,query(1,1,n,id[top[x]],id[x]));        x=fa[top[x]];    }    if(dep[x]>dep[y])swap(x,y);    if(x!=y)ans=max(ans,query(1,1,n,id[x]+1,id[y]));    return ans;}int main(){    //freopen("in.txt","r",stdin);    int i,j,group,x,y,v,Case=0;    group=read();    while(group--){        ini();        n=read();        for(i=1;i<n;++i){            scanf("%d%d%d",&x,&y,&v);            edge[i].x=x,edge[i].y=y,edge[i].v=v;            add(x,y,v);        }        dfs1(1,1,1);        dfs2(1,1);        build(1,1,n);        for(i=1;i<n;i++){            if(dep[edge[i].x]<dep[edge[i].y])                swap(edge[i].x,edge[i].y);            pos=id[edge[i].x];            add(1,1,n,edge[i].v);        }        while(scanf("%s",str)!=EOF){            if(str[0]==‘D‘)break;            x=read();y=read();            if(str[0]==‘Q‘){                printf("%d\n",lca(x,y));            }            else{                pos=id[edge[x].x];                add(1,1,n,y);            }        }        printf("\n");    }    return 0;}