#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 5e4 + 5, MAXM = 1e5 + 5, MAXL = 16;
typedef pair<int, int> pii;

#define mp make_pair
#define u first
#define w second

struct edge{
  int u, v, w;
  bool operator<(const edge &rhs) const{
    return w < rhs.w;
  }
} E[MAXM];

int T, N, M, Q, t = 1, L[MAXN], dp[MAXN][MAXL], MAX[MAXN][MAXL], p[MAXN], h[MAXN];
vector<pii> adj[MAXN];

int find(int u){
  if(p[u] == u) return u;
  return p[u] = find(p[u]);
}

void unite(int u, int v){
  if(h[u] > h[v]) p[v] = u;
  else if(h[v] > h[u]) p[u] = v;
  else p[v] = u, h[u]++;
}

void build(int u, int p){
  for(int i=0; i<adj[u].size(); ++i){
    int v = adj[u][i].u, w = adj[u][i].w;
    if(v != p){
      L[v] = L[u] + 1, dp[v][0] = u, MAX[v][0] = w;
      build(v, u);
    }
  }
}

int query(int u, int v){
  if(L[u] < L[v]) swap(u, v);
  int log = 1, resu = 0, resv = 0;
  for(; (1<<log)<=L[u]; ++log);
  log--;
  for(int i=log; i>=0; --i)
    if(L[u] - (1<<i) >= L[v]){ resu = max(resu, MAX[u][i]); u = dp[u][i]; }
  if(u == v) return resu;
  for(int i=log; i>=0; --i)
    if(dp[u][i] != dp[v][i] && dp[u][i] != -1){
      resu = max(resu, MAX[u][i]), resv = max(resv, MAX[v][i]);
      u = dp[u][i], v = dp[v][i];
    }
  return max(max(resu, MAX[u][0]), max(resv, MAX[v][0]));
}

int main(){
  scanf("%d", &T);
  while(T--){
    int u, v, w;
    scanf("%d %d", &N, &M);
    for(int i=1; i<=M; ++i){ scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].w); E[i].u--, E[i].v--; }
    sort(E + 1, E + M + 1);
    for(int i=0; i<N; ++i){
      adj[i].clear();
      L[i] = 0, p[i] = i, h[i] = 0;
      for(int j=0; (1<<j)<N; ++j) dp[i][j] = MAX[i][j] = -1;
    }
    for(int i=1; i<=M; ++i){
      u = find(E[i].u), v = find(E[i].v), w = E[i].w;
      if(u == v) continue;
      unite(u, v);
      u = E[i].u, v = E[i].v;
      adj[u].push_back(mp(v, w));
      adj[v].push_back(mp(u, w));
    }
    build(0, -1);
    for(int j=1; (1<<j)<N; ++j)
      for(int i=0; i<N; ++i)
        if(dp[i][j - 1] != -1){
          dp[i][j] = dp[dp[i][j - 1]][j - 1], MAX[i][j] = max(MAX[i][j - 1], MAX[dp[i][j - 1]][j - 1]);
        }
    scanf("%d", &Q);
    printf("Case %d:\n", t++);
    while(Q--){
      scanf("%d %d", &u, &v);
      printf("%d\n", query(u - 1, v - 1));
    }
  }
  return 0;
}