1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cassert>
  5 using namespace std;
  6 template <typename T> inline void chkmax(T &a, T b){ if(a < b) a = b;}
  7 // build tree
  8 const int V = 10005;
  9 const int E = V*2;
 10 int head[V], nxt[E], pnt[E], e, n, cost[E];
 11 void add_edge(int u,int v,int c){
 12     nxt[e] = head[u];
 13     head[u] = e;
 14     pnt[e] = v;
 15     cost[e] = c;
 16     e++;
 17 }
 18 // segment tree & prepare
 19 const int inf = ~0u>>2;
 20 int seg[E<<2], parent[V], M, UP[V], heavy[V], num[E], deep[V], P[V], sz[V], segsz;
 21 void ins(int pos,int val){
 22     pos += M; 
 23     seg[pos] = val;
 24     while(pos>>=1) {
 25         seg[pos] = max(seg[pos<<1], seg[pos<<1|1]);
 26     }
 27 }
 28 int find(int u){ return u==parent[u] ? u: parent[u] = find(parent[u]);}
 29 int rmq(int l,int r){
 30     int ans = -inf;
 31     for(l += M-1, r += M+1; l^r^1; l>>=1, r>>=1){
 32         if(~l&1) chkmax(ans,seg[l^1]);
 33         if(r&1) chkmax(ans,seg[r^1]);
 34     }
 35     return ans;
 36 }
 37 void dfs(int u,int f){
 38     int mx = 0 ,s = -1;
 39     sz [u] = 1;
 40     for(int i= head[u]; i!=-1; i=nxt[i]){
 41         int v = pnt[i];
 42         if(v == f) continue;
 43         P[v] = i^1;
 44         deep[v] = deep[u]+1;
 45         dfs(v,u);
 46         sz[u] += sz[v];
 47         if(sz[v] > mx){
 48             mx = sz[v];
 49             s = i;
 50         }
 51     }
 52     heavy[u] = s;
 53     if(s != -1){
 54         parent[pnt[s]] = u;
 55     }
 56 }
 57 void prepare(){
 58     for(int i =30; i;i--) if((1<<i) > n) M = 1<<i;
 59     for(int i = M; i<2*M; i++) seg[i] = -inf;
 60     memset(num,-1,sizeof(num));
 61     segsz = deep[0] = 0;
 62     for(int i=0;i<n;i++) parent[i] = i;
 63     dfs(0,0);
 64 //    for(int i=0;i<n;i++) cout<<deep[i]<<" "; cout<<endl;
 65     for(int i=0; i<n; i++) if(heavy[i] == -1){
 66         int pos = i;
 67 //        cout<<"i:"<<i<<endl;
 68         while(pos && pnt[heavy[pnt[P[pos]]]] == pos){
 69             int t = P[pos];
 70 //            cout<<"pos : "<<pos<<" "<<t<<endl;
 71             num[t^1] = num[t] = ++segsz;
 72             ins(segsz,cost[t]);
 73             pos = pnt[P[pos]];
 74             //cout<<pos<<" "<<pnt[P[pos]]<<" "<<pnt[heavy[pnt[P[pos]]]]<<endl;
 75         }
 76     }
 77 //    for(int i=0;i<e;i++) cout<<num[i]<<" ";cout<<endl;
 78 }
 79 // operator
 80 void change(int pos,int val){
 81     if(num[pos] == -1) { cost[pos] = cost[pos^1] = val; return;}
 82     ins(num[pos],val);
 83 }
 84 int query(int u,int v){
 85     //cout<<u<<" "<<v<<endl;
 86     int ans = -inf;
 87     while(u!=v){
 88         int r = P[u];
 89         if(num[r] == -1){
 90             chkmax(ans,cost[r]);
 91             u = pnt[r];
 92         }
 93         else {
 94             int p = parent[u];
 95             if(deep[p] < deep[v]) p = v;
 96             u = p;
 97             //cout<<r<<" "<<heavy[p]<<endl;
 98             int l = num[heavy[p]]; r = num[r];
 99     //        cout<<"query : "<<l<<" "<<r<<endl;
100             assert(l>0 && l>=r);
101             int t = rmq(r,l);
102             chkmax(ans,t);
103         }
104     }
105     return ans;
106 }
107 int lca(int u,int v){
108     while(1){
109         int a = find(u) , b = find(v);
110         if(a == b) return deep[u]< deep[v] ? u : v;
111         else if(deep[a] >= deep[b]) u = pnt[P[a]]; else v = pnt[P[b]];
112     }
113 }
114 int ask(int u,int v){
115     int p = lca(u,v);
116     return max(query( u, p),query( v, p));
117 }
118 int main(){
119     int t; cin >> t;
120     while(t--){
121         int u,v,c; scanf("%d",&n);
122         e = 0; memset(head,-1,sizeof(head));
123         for(int i=1;i<n;i++){
124             scanf("%d%d%d",&u,&v,&c);
125             u--;v--;
126             add_edge(u,v,c);
127             add_edge(v,u,c);
128         }
129         prepare();
130         char ch[20];
131         while(scanf("%s",ch) && strcmp(ch,"DONE")){
132             if(ch[0]=='C'){
133                 scanf("%d%d",&u,&c);
134                 change((u-1)*2,c);
135             }
136             else {
137                 scanf("%d%d",&u,&v);
138                 printf("%d\n",ask(u-1,v-1));
139             }
140         }
141     }
142 }
143