> {$M 64000000}
> program MiameRishio;
> const
>         maxn                            = 10000;
>         maxm                            = maxn shl 1;
>         maxlg                           = 17;
>         maxtree                         = maxn * 8;
>         maxst                           = maxn * 2;
>         maxvalue                        = maxlongint;
> type
>         edgetype                        = record
>                                             go , pre , len : longint;
>                                           end;
>         treetype                        = record
>                                             sign         : boolean;
>                                             max , min    : longint;
>                                             left , right : longint;
>                                           end;
> var
>         test , n , e , stsize , po      : longint;
>         tree1 , tree2                   : longint;
>         last , depth , sum              : array [ 1..maxn ] of longint;
>         get , go , fa2 , treeroot       : array [ 1..maxn ] of longint;
>         len                             : array [ 0..maxn ] of longint;
>         sa_st , sa_point , sa_edge , fa : array [ 0..maxn ] of longint;
>         treeposi , treefirst , size     : array [ 1..maxn ] of longint;
>         treebelong                      : array [ 0..maxn ] of longint;
>         st , lg                         : array [ 1..maxst ] of longint;
>         visited                         : array [ 1..maxst ] of boolean;
>         edge                            : array [ 0..maxm ] of edgetype;
>         tree                            : array [ 0..maxtree ] of treetype;
>         f                               : array [ 0..maxlg , 1..maxst ] of longint;
> 
> procedure add_edge ( t1 , t2 , t3 : longint );
> begin
>   inc ( e );
>   edge [ e ] . go := t2;
>   edge [ e ] . pre := last [ t1 ];
>   edge [ e ] . len := t3;
>   last [ t1 ] := e;
>   inc ( e );
>   edge [ e ] . go := t1;
>   edge [ e ] . pre := last [ t2 ];
>   edge [ e ] . len := t3;
>   last [ t2 ] := e;
> end;
> 
> function fmax ( a , b : longint ) : longint;
> begin
>   if a > b then fmax := a else fmax := b;
> end;
> 
> function fmin ( a , b : longint ) : longint;
> begin
>   if a < b then fmin := a else fmin := b;
> end;
> 
> procedure init;
> var
>         i               : longint;
>         t1 , t2 , t3    : longint;
> 
> begin
>   readln;
>   readln ( n );
>   for i := 1 to n do
>   begin
>     last [ i ] := 0;
>     fa [ i ] := 0;
>     go [ i ] := 0;
>     depth [ i ] := 0;
>     treebelong [ i ] := 0;
>   end;
> 
>   e := 0;
>   for i := 1 to n - 1 do
>   begin
>     readln ( t1 , t2 , t3 );
>     add_edge ( t1 , t2 , t3 );
>   end;
> end;
> 
> procedure dfs ( step , root , lastedge : longint );
> var
>         w , tmp , node  : longint;
> 
> begin
>   depth [ root ] := step;
>   inc ( stsize );
>   st [ stsize ] := root;
>   sa_st [ root ] := stsize;
>   sum [ root ] := 0;
>   sa_point [ root ] := ( lastedge + 1 ) shr 1;
>   sa_edge [ ( lastedge + 1 ) shr 1 ] := root;
>   len [ ( lastedge + 1 ) shr 1 ] := edge [ lastedge ] . len;
>   tmp := 0;   node := 0;
>   w := last [ root ];
>   while w <> 0 do
>   begin
>     if depth [ edge [ w ] . go ] = 0 then
>     begin
>       dfs ( step + 1 , edge [ w ] . go , w );
>       inc ( stsize );
>       st [ stsize ] := root;
>       fa2 [ edge [ w ] . go ] := root;
>       if sum [ edge [ w ] . go ] > tmp then
>       begin
>         tmp := sum [ edge [ w ] . go ];
>         node := edge [ w ] . go;
>       end;
>       inc ( sum [ root ] , sum [ edge [ w ] . go ] );
>     end;
>     w := edge [ w ] . pre;
>   end;
>   if node <> 0 then
>   begin
>     fa [ node ] := root;
>     go [ root ] := node;
>   end;
>   inc ( sum [ root ] );
> end;
> 
> procedure pass ( x : longint );
> var
>         i               : longint;
>         ch              : char;
> 
> begin
>   for i := 1 to x do read ( ch );
> end;
> 
> procedure build_RMQ;
> var
>         i , j , len     : longint;
> 
> begin
>   j := 0;
>   for i := 1 to stsize do
>   begin
>     while 1 shl ( j + 1 ) <= i do inc ( j );
>     lg [ i ] := j;
>   end;
>   for i := 1 to stsize do f [ 0 , i ] := st [ i ];
>   for i := 1 to maxlg do
>   begin
>     len := 1 shl i;
>     for j := 1 to stsize - len + 1 do
>     begin
>       if depth [ f [ i - 1 , j ] ] < depth [ f [ i - 1 , j + len shr 1 ] ] then f [ i , j ] := f [ i - 1 , j ]
>       else f [ i , j ] := f [ i - 1 , j + len shr 1 ];
>     end;
>   end;
> end;
> 
> procedure swap ( var a , b : longint );
> var
>         tmp             : longint;
> 
> begin
>   tmp := a;
>   a := b;
>   b := tmp;
> end;
> 
> function get_RMQ ( a , b : longint ) : longint;
> var
>         j               : longint;
> 
> begin
>   if a = b then exit ( a );
>   if a > b then swap ( a , b );
>   j := lg [ ( b - a + 1 ) ];
>   get_RMQ := fmin ( f [ j , a ] , f [ j , b - 1 shl j + 1 ] );
> end;
> 
> procedure get_tree ( root : longint );
> begin
>   if root = 0 then exit;
>   if fa [ root ] <> 0 then
>   begin
>     inc ( tree2 );
>     get [ tree2 ] := sa_point [ root ];
>     treeposi [ sa_point [ root ] ] := tree2;
>     treebelong [ get [ tree2 ] ] := tree1;
>   end;
>   get_tree ( go [ root ] );
>   visited [ root ] := true;
> end;
> 
> procedure build_tree ( x , left , right : longint );
> var
>         mid             : longint;
> 
> begin
>   inc ( po );
>   if left = right then
>   begin
>     inc ( e );
>     tree [ x ] . max := len [ get [ e ] ];
>     tree [ x ] . min := len [ get [ e ] ];
>     tree [ x ] . left := 0;
>     tree [ x ] . right := 0;
>     tree [ x ] . sign := false;
>     exit;
>   end;
>   mid := ( left + right ) shr 1;
>   tree [ x ] . left := po + 1;
>   build_tree ( po + 1 , left , mid );
>   tree [ x ] . right := po + 1;
>   build_tree ( po + 1 , mid + 1 , right );
>   tree [ x ] . max := fmax ( tree [ tree [ x ] . left ] . max , tree [ tree [ x ] . right ] . max );
>   tree [ x ] . min := fmin ( tree [ tree [ x ] . left ] . min , tree [ tree [ x ] . right ] . min );
>   tree [ x ] . sign := false;
> end;
> 
> procedure build_segment_tree;
> var
>         i               : longint;
> 
> begin
>   fillchar ( visited , sizeof ( visited ) , false );
>   tree1 := 0;
>   po := 0;
>   for i := 1 to stsize do
>     if ( not visited [ st [ i ] ] ) and ( go [ st [ i ] ] <> 0 ) then
>     begin
>       inc ( tree1 );
>       tree2 := 0;
>       get_tree ( st [ i ] );
>       e := 0;
>       treeroot [ tree1 ] := po + 1;
>       treefirst [ tree1 ] := st [ i ];
>       size [ tree1 ] := tree2;
>       build_tree ( po + 1 , 1 , tree2 );
>     end;
> end;
> 
> procedure maintain ( x , left ,right : longint );
> var
>         lc , rc , tmp   : longint;
> 
> begin
>   if tree [ x ] . sign then
>   begin
>     tree [ x ] . sign := false;
>     if left <> right then
>     begin
>       tree [ tree [ x ] . left ] . sign := not tree [ tree [ x ] . left ] . sign;
>       tree [ tree [ x ] . right ] . sign := not tree [ tree [ x ] . right ] . sign;
>     end;
>     tmp := tree [ x ] . max;
>     tree [ x ] . max := -tree [ x ] . min;
>     tree [ x ] . min := -tmp;
>   end;
> end;
> 
> function tree_find ( x , left , right , t1 , t2 : longint ) : longint;
> var
>         mid , tmp       : longint;
> 
> begin
>   maintain ( x , left , right );
>   if ( t1 <= left ) and ( right <= t2 ) then exit ( tree [ x ] . max );
>   mid := ( left + right ) shr 1;
>   tmp := -maxvalue;
>   if ( t1 <= mid ) and ( left <= t2 ) then tmp := fmax ( tmp , tree_find ( tree [ x ] . left , left , mid , t1 , t2 ) );
>   if ( t1 <= right ) and ( mid + 1 <= t2 ) then tmp := fmax ( tmp , tree_find ( tree [ x ] . right , mid + 1 , right , t1 , t2 ) );
>   tree_find := tmp;
> end;
> 
> function _query_get ( a , b : longint ) : longint;
> var
>         tmp             : longint;
> 
> begin
>   tmp := -maxvalue;
>   repeat
>     if depth [ a ] <= depth [ b ] then break;
>     if fa [ a ] = 0 then
>     begin
>       tmp := fmax ( tmp , len [ sa_point [ a ] ] );
>       a := fa2 [ a ];
>     end
>     else
>     begin
>       if treebelong [ sa_point [ a ] ] <> treebelong [ sa_point [ b ] ] then tmp := fmax ( tmp , tree_find ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , 1 , treeposi [ sa_point [ a ] ] ) )
>       else tmp := fmax ( tmp , tree_find ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , treeposi [ sa_point [ b ] ] + 1 , treeposi [ sa_point [ a ] ] ) );
>       a := treefirst [ treebelong [ sa_point [ a ] ] ];
>     end;
>   until false;
>   _query_get := tmp;
> end;
> 
> function _query ( a , b : longint ) : longint;
> var
>         ance , u , v    : longint;
> 
> begin
>   ance := get_RMQ ( sa_st [ a ] , sa_st [ b ] );
>   u := _query_get ( a , ance );
>   v := _query_get ( b , ance );
>   writeln ( fmax ( u , v ) );
> end;
> 
> procedure tree_modify ( x , left , right , k , t : longint );
> var
>         mid             : longint;
> 
> begin
>   maintain ( x , left , right );
>   if left = right then
>   begin
>     tree [ x ] . max := t;
>     tree [ x ] . min := t;
>     exit;
>   end;
>   mid := ( left + right ) shr 1;
>   if k <= mid then tree_modify ( tree [ x ] . left , left , mid , k , t )
>   else tree_modify ( tree [ x ] . right , mid + 1 , right , k , t );
>   tree [ x ] . max := fmax ( tree [ tree [ x ] . left ] . max , tree [ tree [ x ] . right ] . max );
>   tree [ x ] . min := fmin ( tree [ tree [ x ] . left ] . min , tree [ tree [ x ] . right ] . min );
> end;
> 
> procedure _change ( a , b : longint );
> begin
>   if fa [ sa_edge [ a ] ] = 0 then len [ a ] := b
>   else tree_modify ( treeroot [ treebelong [ a ] ] , 1 , size [ treebelong [ a ] ] , treeposi [ a ] , b );
> end;
> 
> procedure tree_insert ( x , left , right , t1 , t2 : longint );
> var
>         mid             : longint;
> 
> begin
>   maintain ( x , left , right );
>   if ( t1 <= left ) and ( right <= t2 ) then
>   begin
>     tree [ x ] . sign := true;
>     maintain ( x , left , right );
>     exit;
>   end;
>   mid := ( left + right ) shr 1;
>   if ( t1 <= mid ) and ( left <= t2 ) then tree_insert ( tree [ x ] . left , left , mid , t1 , t2 );
>   if ( t1 <= right ) and ( mid + 1 <= t2 ) then tree_insert ( tree [ x ] . right , mid + 1 , right , t1 , t2 );
>   tree [ x ] . max := fmax ( tree [ tree [ x ] . left ] . max , tree [ tree [ x ] . right ] . max );
>   tree [ x ] . min := fmin ( tree [ tree [ x ] . left ] . min , tree [ tree [ x ] . right ] . min );
> end;
> 
> procedure _negate_get ( a , b : longint );
> begin
>   repeat
>     if depth [ a ] <= depth [ b ] then break;
>     if fa [ a ] = 0 then
>     begin
>       len [ sa_point [ a ] ] := - len [ sa_point [ a ] ];
>       a := fa2 [ a ];
>     end
>     else
>     begin
>       if treebelong [ sa_point [ a ] ] <> treebelong [ sa_point [ b ] ] then tree_insert ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , 1 , treeposi [ sa_point [ a ] ] )
>       else tree_insert ( treeroot [ treebelong [ sa_point [ a ] ] ] , 1 , size [ treebelong [ sa_point [ a ] ] ] , treeposi [ sa_point [ b ] ] + 1 , treeposi [ sa_point [ a ] ] );
>       a := treefirst [ treebelong [ sa_point [ a ] ] ];
>     end;
>   until false;
> end;
> 
> procedure _negate ( a , b : longint );
> var
>         ance , u , v    : longint;
> 
> begin
>   ance := get_RMQ ( sa_st [ a ] , sa_st [ b ] );
>   _negate_get ( a , ance );
>   _negate_get ( b , ance );
> end;
> 
> procedure main;
> var
>         ch              : char;
>         t1 , t2         : longint;
> 
> begin
>   stsize := 0;
>   dfs ( 1 , 1 , 0 );
>   sa_edge [ 0 ] := 0;
>   build_segment_tree;
>   build_RMQ;
>   repeat
>     read ( ch );
>     case ch of
>       'Q' : begin
>               pass ( 4 );
>               readln ( t1 , t2 );
>               _query ( t1 , t2 );
>             end;
> 
>       'C' : begin
>               pass ( 5 );
>               readln ( t1 , t2 );
>               _change ( t1 , t2 );
>             end;
> 
>       'N' : begin
>               pass ( 5 );
>               readln ( t1 , t2 );
>               _negate ( t1 , t2 );
>             end;
> 
>       'D' : begin
>               pass ( 3 );
>               readln;
>               exit;
>             end;
>     end;
>   until false;
> end;
> 
> begin
>   assign ( input , 'pku3237.in' );
>   assign ( output , 'pku3237.out' );
>   reset ( input );
>   rewrite ( output );
>   readln ( test );
>   for test := 1 to test do
>   begin
>     init;
>     main;
>   end;
>   close ( input );
>   close ( output );
> end.