UVa 10342

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

int edge[100][100];
int dist[100][100];
int dist2[100][100];

int32_t main(){
    int n, m, q, cnt = 0;
    while(cin >> n >> m){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(i != j)dist[i][j] = edge[i][j] = 1e8;
                else dist[i][j] = edge[i][j] = 0;
                dist2[i][j] = 1e8;
            }
        }
        for(int i = 0; i < m; ++i){
            int u,v,w;
            cin >> u >> v >> w;
            edge[u][v] = w;
            edge[v][u] = w;
            dist2[u][u] = min(dist2[u][u], w*2);
            dist2[v][v] = min(dist2[v][v], w*2);
        }
        for(int k = 0; k < n; ++k){
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j){
                    dist[i][j] = min(dist[i][j], min(edge[i][k], dist[i][k]) + min(edge[k][j], dist[k][j]));
                }
            }
        }
        for(int k = 0; k < n; ++k){
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j){
                    int ik = (dist[i][k] == edge[i][k])? dist2[i][k] : min(edge[i][k], dist2[i][k]);//second shortest path between i,k
                    int kj = (dist[k][j] == edge[k][j])? dist2[k][j] : min(edge[k][j], dist2[k][j]);//second shortest path between k,j
                    if(dist[i][j] != dist[i][k] + dist[k][j])dist2[i][j] = min(dist2[i][j], dist[i][k] + dist[k][j]);
                    dist2[i][j] = min(dist2[i][j], ik + dist[k][j]);
                    dist2[i][j] = min(dist2[i][j], dist[i][k] + kj);
                }
            }
        }
        /*debugsssss
        cout << "dist\n";
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cout << dist[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl << "dist2\n";
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cout << dist2[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl << "bet\n";
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                (dist[i][j] == edge[i][j])? cout << dist2[i][j] : cout << min(edge[i][j], dist2[i][j]);
                //cout << edge[i][j];
                cout << ' ';
            }
            cout << endl;
        }
        */
        cout << "Set #" << ++cnt << '\n';
        cin >> q;
        while(q--){
            int u,v;
            cin >> u >> v;
            int ans = dist2[u][v];
            if(ans == 1e8)cout << "?\n";
            else cout << ans << '\n';
        }
    }
    return 0 ;
}