const oo=;

 var t:array[..]of record

                           min,max,tag:longint;

                          end;

     f:array[..,..]of longint;

     head,vet,next,dep,tid,id,flag,

     len,son,size,top,a,b,c,d,g,h:array[..]of longint;

     n,m,i,tot,x,y,k,v,cas,time,z,s,tmp,fuhao:longint;

     ch:string;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function max(x,y:longint):longint;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 procedure add(a,b,c:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  len[tot]:=c;

  head[a]:=tot;

 end;

 procedure dfs(u:longint);

 var e,v,i,t:longint;

 begin

  for i:= to  do

  begin

   if dep[u]<(<<i) then break;

   f[u,i]:=f[f[u,i-],i-];

  end;

  e:=head[u]; flag[u]:=; size[u]:=; son[u]:=; t:=;

  while e<> do

  begin

   v:=vet[e];

   if flag[v]= then

   begin

    dep[v]:=dep[u]+;

    f[v,]:=u;

    dfs(v);

    size[u]:=size[u]+size[v];

    if size[v]>t then

    begin

     t:=size[v]; son[u]:=v;

    end;

   end;

   e:=next[e];

  end;

 end;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 function lca(x,y:longint):longint;

 var i,d:longint;

 begin

  if dep[x]<dep[y] then swap(x,y);

  d:=dep[x]-dep[y];

  for i:= to  do

   if d and (<<i)> then x:=f[x,i];

  for i:= downto  do

   if f[x,i]<>f[y,i] then

   begin

    x:=f[x,i]; y:=f[y,i];

   end;

  if x=y then exit(x);

  exit(f[x,]);

 end;

 procedure pushdown(l,r,p:longint);

 var mid,tmp,t1,t2:longint;

 begin

  tmp:=t[p].tag;

  if (l=r)or(tmp=) then exit;

  t[p].tag:=;

  t1:=t[p<<].min; t2:=t[p<<].max;

  t[p<<].max:=-t1; t[p<<].min:=-t2;

  t1:=t[p<<+].min; t2:=t[p<<+].max;

  t[p<<+].max:=-t1; t[p<<+].min:=-t2;

  t[p<<].tag:=--t[p<<].tag; t[p<<+].tag:=--t[p<<+].tag;

 end;

 procedure pushup(p:longint);

 begin

  t[p].min:=min(t[p<<].min,t[p<<+].min);

  t[p].max:=max(t[p<<].max,t[p<<+].max);

 end;

 procedure change(l,r,x,v,p:longint);

 var mid:longint;

 begin

  pushdown(l,r,p);

  if (l=x)and(r=x) then

  begin

   t[p].min:=v; t[p].max:=v;

  // t[p].tag:=v;

   exit;

  end;

  mid:=(l+r)>>;

  if x<=mid then change(l,mid,x,v,p<<)

   else change(mid+,r,x,v,p<<+);

  pushup(p);

 end;

 procedure dfs2(u,ance:longint);

 var e,v:longint;

 begin

  flag[u]:=; inc(time); tid[u]:=time; id[time]:=u; top[u]:=ance;

  if son[u]> then dfs2(son[u],ance);

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if flag[v]= then dfs2(v,v);

   e:=next[e];

  end;

 end;

 procedure build(l,r,p:longint);

 var mid:longint;

 begin

  if l=r then

  begin

   if h[id[l]]>oo then

   begin

    t[p].min:=oo; t[p].max:=-oo;

   end

    else begin t[p].min:=h[id[l]]; t[p].max:=h[id[l]]; end;

   t[p].tag:=;

   exit;

  end;

  mid:=(l+r)>>;

  build(l,mid,p<<);

  build(mid+,r,p<<+);

  pushup(p);

 end;

 function query(l,r,x,y,p:longint):longint;

 var mid,t1,t2:longint;

 begin

  pushdown(l,r,p);

  if (l>=x)and(r<=y) then exit(t[p].max);

  mid:=(l+r)>>; query:=-oo;

  if x<=mid then query:=max(query,query(l,mid,x,y,p<<));

  if y>mid then query:=max(query,query(mid+,r,x,y,p<<+));

  pushup(p);

 end;

 procedure negate(l,r,x,y,p:longint);

 var mid,t1,t2:longint;

 begin

  pushdown(l,r,p);

  if (l>=x)and(r<=y) then

  begin

   t1:=t[p].min; t2:=t[p].max;

   t[p].min:=-t2; t[p].max:=-t1;

   t[p].tag:=-;

   exit;

  end;

  mid:=(l+r)>>;

  if x<=mid then negate(l,mid,x,y,p<<);

  if y>mid then negate(mid+,r,x,y,p<<+);

  pushup(p);

 end;

 procedure ngt(x,y:longint);

 var q:longint;

 begin

  q:=lca(x,y);

  while top[x]<>top[q] do

  begin

   negate(,n,tid[top[x]],tid[x],);

   x:=f[top[x],];

  end;

  if tid[q]+<=tid[x] then negate(,n,tid[q]+,tid[x],);

  while top[y]<>top[q] do

  begin

   negate(,n,tid[top[y]],tid[y],);

   y:=f[top[y],];

  end;

  if tid[q]+<=tid[y] then negate(,n,tid[q]+,tid[y],);

 end;

 function ask(x,y:longint):longint;

 var q:longint;

 begin

  q:=lca(x,y);

  ask:=-oo;

  while top[x]<>top[q] do

  begin

   ask:=max(ask,query(,n,tid[top[x]],tid[x],));

   x:=f[top[x],];

  end;

  if tid[q]+<=tid[x] then ask:=max(ask,query(,n,tid[q]+,tid[x],));

  while top[y]<>top[q] do

  begin

   ask:=max(ask,query(,n,tid[top[y]],tid[y],));

   y:=f[top[y],];

  end;

  if tid[q]+<=tid[y] then ask:=max(ask,query(,n,tid[q]+,tid[y],));

 end;

 begin

  assign(input,'tree.in'); reset(input);

  assign(output,'poj3237.out'); rewrite(output);

  readln(cas);

  for v:= to cas do

  begin

   readln(n);

   fillchar(head,sizeof(head),); tot:=; time:=;

   fillchar(flag,sizeof(flag),);

   fillchar(d,sizeof(d),); fillchar(g,sizeof(g),);

   fillchar(h,sizeof(h),$7f); fillchar(dep,sizeof(dep),);

   fillchar(f,sizeof(f),); fillchar(tid,sizeof(tid),);

   fillchar(id,sizeof(id),);

   for i:= to n<< do

   begin

    t[i].min:=oo; t[i].max:=-oo; t[i].tag:=;

   end;

   for i:= to n- do

   begin

    readln(a[i],b[i],c[i]);

    add(a[i],b[i],c[i]);

    add(b[i],a[i],c[i]);

   end;

   dfs();

   fillchar(flag,sizeof(flag),);

   dfs2(,);

   for i:= to n- do

   begin

    if dep[a[i]]<dep[b[i]] then tmp:=b[i]

     else tmp:=a[i];

    d[i]:=tmp; g[tmp]:=i; h[tmp]:=c[i];

   end;

  // h[]:=; d[n]:=; g[]:=n;

   build(,n,);

   while true do

   begin

    readln(ch); x:=; y:=; k:=length(ch);

    if ch[]='D' then break; s:=; fuhao:=;

    for i:= to k do

    begin

     if ch[i]=' ' then begin inc(s); continue; end;

     if (s=)and(ch[i]<>' ') then x:=x*+ord(ch[i])-ord('');

     if (s=)and(ch[i]<>' ') then

     begin

      if ch[i]='-' then begin fuhao:=-; continue; end

       else y:=y*+ord(ch[i])-ord('');

     end;

    end;

    if ch[]='C' then change(,n,tid[d[x]],fuhao*y,);

    if ch[]='N' then ngt(x,y);

    if ch[]='Q' then

    begin

     writeln(ask(x,y));

     //writeln;

    end;

   end;

  end;

  close(input);

  close(output);

 end.