import java.io.*;
import java.math.*;
import java.util.*;
/**
*
* @author Saju
*
*/
public class Main {
private static int dx[] = { 1, 0, -1, 0 };
private static int dy[] = { 0, -1, 0, 1 };
private static final long INF
= Long.
MAX_VALUE; private static final int INT_INF
= Integer.
MAX_VALUE; private static final long NEG_INF
= Long.
MIN_VALUE; private static final int NEG_INT_INF
= Integer.
MIN_VALUE; private static final double EPSILON = 1e-10;
private static final int MAX = 10001;
private static final long MOD = 1000000007;
private static final int MAXN = 10000007;
private static final int MAXA = 10000009;
private static final int MAXLOG = 22;
InputReader in
= new InputReader
(System.
in);
// InputReader in = new InputReader(new FileInputStream("src/test.in"));
// PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("src/test.out")));
/*
2
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
*/
int test = in.nextInt();
StringBuilder sb = new StringBuilder();
HLD hld = new HLD();
for (int t = 1; t <= test; t++) {
int n = in.nextInt();
hld.vertex = n;
hld.clear();
for(int i = 1; i <= n - 1; i++) {
int u = in.nextInt();
int v = in.nextInt();
int w = in.nextInt();
hld.addEdge(u, v, w, i);
}
hld.buildHLD();
while(true) {
if(str.charAt(0) == 'D') {
break;
}
int x = in.nextInt();
int y = in.nextInt();
if(str.charAt(0) == 'Q') {
// out.println(query(x, y));
sb.append(hld.query(x, y) + "\n");
}
else {
hld.update(x, y);;
}
}
}
out.print(sb.toString());
out.flush();
out.close();
}
private static class HLD {
final int MAX = 10001;
final int MAXLOG = 15;
int vertex;
int[][] pp = new int[MAXLOG][MAX];
int[] level = new int[MAX];
int[] tree = new int[MAX << 2];
int[] twoPower = new int[MAXLOG];
int chainNo;
int indexNo;
int[] chainHead = new int[MAX];
int[] chainSize = new int[MAX];
int[] nodeInWhichChain = new int[MAX];
int[] nodeIndexInBaseArray = new int[MAX];
int[] baseArray = new int[MAX];
int[] edgeIndex = new int[MAX];
int[] subtreeSize = new int[MAX];
public HLD() {
for (int i = 0; i < MAX; i++) {
adj[i] = new ArrayList<>();
}
twoPower[0] = 1;
for (int i = 1; i < MAXLOG; i++) {
twoPower[i] = twoPower[i - 1] << 1;
}
}
public void clear() {
for (int i = 1; i <= vertex; i++) {
adj[i].clear();
}
for (int i = 1; i <= vertex; i++) {
chainHead[i] = -1;
chainSize[i] = -1;
}
for (int i = 0; i < MAXLOG; i++) {
for (int j = 1; j <= vertex; j++) {
pp[i][j] = -1;
}
}
}
public void addEdge(int u, int v, int w, int idx) {
adj[u].add(new Edge(v, w, idx));
adj[v].add(new Edge(u, w, idx));
}
public void buildHLD() {
indexNo = 0;
chainNo = 1;
dfs(1, -1, 0);
sparseTable();
hld(1, -1, 0);
build(1, 1, vertex);
}
public void update(int idx, int val) {
update(1, 1, vertex, edgeIndex[idx], val);
}
public int query(int u, int v) {
int lca = lca(u, v);
int val1 = hldQuery(lca, u);
int val2 = hldQuery(lca, v);
return max(val1, val2);
}
private int hldQuery(int u, int v) {
if (u == v) {
return 0;
}
int ans = 0;
while (true) {
if (nodeInWhichChain[u] == nodeInWhichChain[v]) {
int start = nodeIndexInBaseArray[u];
int end = nodeIndexInBaseArray[v];
if (start < end) {
ans = max(ans, query(1, 1, vertex, start + 1, end));
}
return ans;
}
int head = chainHead[nodeInWhichChain[v]];
int start = nodeIndexInBaseArray[head];
int end = nodeIndexInBaseArray[v];
ans = max(ans, query(1, 1, vertex, start, end));
v = pp[0][head];
}
}
private void dfs(int u, int parent, int d) {
pp[0][u] = parent;
subtreeSize[u] = 1;
level[u] = d;
for (Edge e : adj[u]) {
if (e.v != parent) {
dfs(e.v, u, d + 1);
subtreeSize[u] += subtreeSize[e.v];
}
}
}
private void sparseTable() {
for (int i = 1; i < MAXLOG; i++) {
for (int j = 1; j <= vertex; j++) {
if (pp[i - 1][j] != -1) {
pp[i][j] = pp[i - 1][pp[i - 1][j]];
}
}
}
}
private void hld(int u, int parent, int cost) {
indexNo++;
nodeIndexInBaseArray[u] = indexNo;
nodeInWhichChain[u] = chainNo;
baseArray[indexNo] = cost;
chainSize[chainNo]++;
if (chainHead[chainNo] == -1) {
chainHead[chainNo] = u;
}
int specialChild = -1;
int specialCost = -1;
int specialIdx = -1;
int maxSubtreeSize = 0;
for (Edge e : adj[u]) {
int v = e.v;
if (v != parent) {
if (maxSubtreeSize < subtreeSize[v]) {
maxSubtreeSize = subtreeSize[v];
specialChild = v;
specialCost = e.w;
specialIdx = e.idx;
}
}
}
if (specialChild != -1) {
edgeIndex[specialIdx] = indexNo + 1;
hld(specialChild, u, specialCost);
}
for (Edge e : adj[u]) {
int v = e.v;
if (v != parent && v != specialChild) {
chainNo++;
edgeIndex[e.idx] = indexNo + 1;
hld(v, u, e.w);
}
}
}
private void build(int node, int left, int right) {
// System.out.println(left + " " + right);
if (left == right) {
tree[node] = baseArray[left];
return;
}
int mid = (left + right) >> 1;
int leftNode = node << 1;
int rightNode = leftNode | 1;
build(leftNode, left, mid);
build(rightNode, mid + 1, right);
tree[node] = max(tree[leftNode], tree[rightNode]);
}
private void update(int node, int left, int right, int idx, int val) {
if (left == right && idx == left) {
tree[node] = val;
} else {
int mid = (left + right) >> 1;
int leftNode = node << 1;
int rightNode = leftNode | 1;
if (idx <= mid) {
update(leftNode, left, mid, idx, val);
} else {
update(rightNode, mid + 1, right, idx, val);
}
tree[node] = max(tree[leftNode], tree[rightNode]);
}
}
private int query(int node, int left, int right, int start, int end) {
if (left > right || left > end || right < start) {
return 0;
}
if (left >= start && right <= end) {
return tree[node];
}
int mid = (left + right) >> 1;
int leftNode = node << 1;
int rightNode = leftNode | 1;
int val1 = query(leftNode, left, mid, start, end);
int val2 = query(rightNode, mid + 1, right, start, end);
return max(val1, val2);
}
private int lca(int p, int q) {
if(p == q) {
return p;
}
if (level[p] < level[q]) {
int temp = p;
p = q;
q = temp;
}
for (int i = MAXLOG - 1; i >= 0; i--) {
if ((level[p] - twoPower[i]) >= level[q]) {
p = pp[i][p];
}
}
if (p == q) {
return p;
}
for (int i = MAXLOG - 1; i >= 0; i--) {
if (pp[i][p] != pp[i][q] && pp[i][p] != -1) {
p = pp[i][p];
q = pp[i][q];
}
}
return pp[0][p];
}
private static class Edge {
int v;
int w;
int idx;
Edge() {
}
Edge(int v, int w, int idx) {
this.v = v;
this.w = w;
this.idx = idx;
}
}
}
private static long bigMod(long n, long k, long m) {
long ans = 1;
while (k > 0) {
if ((k & 1) == 1) {
ans = (ans * n) % m;
}
n = (n * n) % m;
k >>= 1;
}
return ans;
}
private static int ceil(int n, int x) {
int div = n / x;
if(div * x != n) {
div++;
}
return div;
}
private static class Point { double x;
double y;
Point(double x,
double y
) { this.x = x;
this.y = y;
}
double getDistance
(Point p2
) { double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
return Math.
sqrt((dx
* dx
) + (dy
* dy
)); }
}
private static int abs(int x) {
if (x < 0) {
return -x;
}
return x;
}
private static long abs(long x) {
if(x < 0) {
return -x;
}
return x;
}
private static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
private static int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
private static int log(long x, int base) {
return (int) (Math.
log(x
) / Math.
log(base
)); }
private static long min(long a, long b) {
if (a < b) {
return a;
}
return b;
}
private static int min(int a, int b) {
if (a < b) {
return a;
}
return b;
}
private static long max(long a, long b) {
if (a < b) {
return b;
}
return a;
}
private static int max(int a, int b) {
if (a < b) {
return b;
}
return a;
}
private static class InputReader {
tokenizer = null;
}
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
}
return null;
}
return tokenizer.nextToken();
}
try {
tokenizer = null;
line = reader.readLine();
}
return line;
}
public int nextInt() {
}
public double nextDouble() {
return Double.
parseDouble(next
()); }
public long nextLong() {
return Long.
parseLong(next
()); }
public boolean hasNext() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
}
return false;
}
return true;
}
}
}