#include <bits/stdc++.h>
using namespace std;

#define HOISE cerr << "hoise" << endl
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define READ freopen("alu.txt", "r", stdin);
#define WRITE freopen("vorta.txt", "w", stdout);
#define MP make_pair
#define PB push_back
#define INF 1e9
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 1e5 + 5;
const int MAXLOG = log2(MAX) + 2;

int n, m;
vector<pii> G[MAX];
int cost[MAX], par[MAX], d[MAX];
pii P[MAX][MAXLOG];

struct edge{
    int u, v, w;
    edge(int u_, int v_, int w_){ u = u_; v = v_; w = w_; }
};
bool operator < (edge x, edge y)
{
    return x.w > y.w;
}

inline void init()
{
    for(int i = 0; i < MAX; i++) G[i].clear();
    memset(par, -1, sizeof par);
}
inline void MST()
{
    bool taken[n+5];
    memset(taken, false, sizeof taken);

    for(int i = 0; i < MAX; i++)
        cost[i] = INF;

    priority_queue<edge> pq;
    pq.push(edge(0, 1, 0));

    while(!pq.empty()){
        edge e = pq.top();
        pq.pop();

        if(cost[e.v] > e.w){
            cost[e.v] = e.w;
            par[e.v] = e.u;
            taken[e.v] = true;
        }

        for(pii nxt : G[e.v]){
            int u = e.v;
            int v = nxt.first;
            int w = nxt.second;
            if(!taken[v] && w < cost[v])
                pq.push(edge(u, v, w));
        }
    }
}
inline void precalcLCS()
{
    memset(P, -1, sizeof P);

    for(int i = 1; i <= n; i++){
        P[i][0].first = par[i];
        P[i][0].second = cost[i];
    }

    for(int j = 1; (1<<j) < n; j++)
        for(int i = 1; i <= n; i++)
            if(P[i][j-1].first != -1){
                P[i][j].first = P[ P[i][j-1].first ][j-1].first;
                P[i][j].second = max(P[i][j-1].second, P[ P[i][j-1].first ][j-1].second);
            }
}
inline int lcs(int u, int v, int &ans)
{
    if(d[u] > d[v]) swap(u, v);

    int dif = d[v] - d[u];
    for(int j = MAXLOG-1; j >= 0 && dif > 0; j--)
        if((1<<j) <= dif){
            dif -= (1<<j);
            ans = max(ans, P[v][j].second);
            v = P[v][j].first;
        }

    if(u == v) return u;

    for(int j = MAXLOG-1; j >= 0; j--){
        if(P[u][j].first != -1 && P[u][j].first != P[v][j].first){
            ans = max(ans, P[u][j].second);
            ans = max(ans, P[v][j].second);
            u = P[u][j].first;
            v = P[v][j].first;
        }
    }

    ans = max(ans, cost[u]);
    ans = max(ans, cost[v]);
    return par[u];
}
void dfs(int u, int depth)
{
    d[u] = depth;
    for(pii nxt : G[u]){
        int v = nxt.first;
        if(v == par[u]) continue;
        if(u == par[v]) dfs(v, depth+1);
    }
}

int main()
{
//    READ WRITE

    int tc;
    scanf("%d", &tc);
    for(int nc = 1; nc <= tc; nc++){
        init();

        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++){
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            G[u].PB(MP(v, w));
            G[v].PB(MP(u, w));
        }

        MST();
        precalcLCS();
        dfs(1, 0);

        printf("Case %d:\n", nc);

        int q;
        scanf("%d", &q);
        while(q--){
            int u, v;
            scanf("%d %d", &u, &v);
            int ans = 0;
            int l = lcs(u, v, ans);
//            cerr << "lcs = " << l << endl;
            printf("%d\n", ans);
        }
    }

    return 0;
}

/*
1
6 6
1 2 73
1 3 64
3 4 10
1 5 36
2 6 55
1 3 89
1
3 6
*/