LCA

#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<endl
#define mp make_pair
#define maxn 50005
#define xx first
#define yy second

vector < pair< int , pair< int , int > > > v;
int n,m;
int parent[maxn];
vector< pair<int, int > > g[maxn];
int dis[maxn],lvl[maxn],par[maxn];
bool vis[maxn];
int sparse_parent[maxn][20],sparse_dist[maxn][20];

int findset(int x){
    if(x!=parent[x]){
        parent[x] = findset(parent[x]);
    }
    return parent[x];
}

void kruskal(){
    for(int i=0; i<=n; i++){
        parent[i] = i;
    }
    sort(v.begin(),v.end());
    for(int i=0; i<v.size(); i++){
        int pu = findset(v[i].second.first);
        int pv = findset(v[i].second.second);
        if(pu!=pv){
            g[v[i].yy.xx].push_back(mp(v[i].yy.yy,v[i].xx));
            g[v[i].yy.yy].push_back(mp(v[i].yy.xx,v[i].xx));
            parent[pu] = pv;
        }
    }
}

void dfs(int src, int parent , int dep){
    vis[src] = true;
    par[src] = parent;
    lvl[src] = dep;
    for(int i=0; i<g[src].size(); i++){
        int x = g[src][i].xx;
        int y = g[src][i].yy;
        if( vis[x] ) continue;
        dis[x] = min(dis[src]+y,dis[x]);
        dfs(x,src,dep+1);
    }
}

void lca_init(){
    memset(sparse_parent,-1,sizeof(sparse_parent));
//  memset(sparse_dist,0,sizeof(sparse_dist));
    for(int i=0; i<n; i++ ){  ///sparse_parent[i][j] : node i er 2^j th parent; sparse_dist[i][j] : node i e 2^j th parent porjonto max weight
        sparse_parent[i][0] = par[i];
        if(par[i]==-1) { sparse_dist[i][0] = dis[i] ; continue; }
        sparse_dist[i][0] = (dis[i] - dis[par[i]]);
       // printf("sparse_dist[%d][%d]: %d\n",i,0,sparse_dist[i][0]);
    }
    for(int j=1; (1<<j)<n; j++){
        for(int i=0; i<n; i++){
            if(sparse_parent[i][j-1]==-1) continue;
            sparse_parent[i][j] = sparse_parent[sparse_parent[i][j-1]][j-1] ;
            sparse_dist[i][j] = max(sparse_dist[i][j-1],sparse_dist[sparse_parent[i][j-1]][j-1]);
         //   printf("sparse_dist[%d][%d]: %d\n",i,j,sparse_dist[i][j]);
        }
    }
}

int lca_query(int p, int q){
    if(lvl[p]<lvl[q]) swap(p,q);
    int log = 1;
    while(true){
        int next = log+1;
        if((1<<next)>lvl[p]) break;
        log++;
    }
    int ret = -1000000;
    for(int i=log; i>=0; i--){  ///same level e niye ashtechi
        if((lvl[p]-(1<<i))>=lvl[q]){
            ret = max(ret,sparse_dist[p][i]);
            p = sparse_parent[p][i];
        }
    }
    if(p==q) return ret;
    for(int i=log; i>=0; i--){
        if(sparse_parent[p][i]!=-1 && sparse_parent[p][i]!=sparse_parent[q][i]){
            ret = max(ret,max(sparse_dist[p][i],sparse_dist[q][i]));
            p = sparse_parent[p][i];
            q = sparse_parent[q][i];
        }
    }
    int x ,y;
    if(par[p]==-1) x = dis[p];
    else x = dis[p]-dis[par[p]];
    if(par[q]==-1) y = dis[q];
    else y = dis[q]-dis[par[q]];
    ret = max(ret,max(x,y));
    return ret;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
//    cout<<log2(maxn)<<endl;
    cin>>t;
    int tc  = 0 ;
    while(t--){
        cin>>n>>m;
        for(int i=1; i<=m; i++){
            int a,b,c;
            cin>>a>>b>>c;
            a--;
            b--;
            v.push_back(mp(c,mp(a,b)));
        }
        kruskal();
        memset(dis,1000000,sizeof(dis));
        memset(vis,false,sizeof(vis));
        dis[0] = 0;
        dfs(0,-1,0);
//        for(int i=0; i<n; i++){
//          cout<<i<<" : "<<dis[i]<<endl;
//        }
        lca_init();
        printf("Case %d:\n",++tc);
        int q;
        cin>>q;
        while(q--){
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            printf("%d\n",lca_query(a,b));
        }
        for(int i=0; i<=n; i++){
            g[i].clear();
        }
        v.clear();
    }
    return 0;
}

/**
2
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
2 1
1 2 100
1
1 2

*/