#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using piit = pair<ll, int>;
const ll inf = numeric_limits<ll>::max() / 2;
const int sz = 1e5 + 10;
const int lgsz = __lg(sz) + 1;
struct edge_k {
    int u, v;
    ll w;
    bool operator<(const edge_k &a) const {
        return w < a.w;
    }
} graph_k[sz];
struct edge {
    int nxt, to;
    ll w;
} tree[sz], graph[100];
int hppt, hppg, headt[sz], headg[sz];
void addEdge(int u, int v, ll weight, edge* g, int& hpp, int* head) {
    g[++hpp] = edge{head[u], v, weight};
    head[u] = hpp;
    g[++hpp] = edge{head[v], u, weight};
    head[v] = hpp;
}
struct UFS {
    vector<int> fa, ssz;
    void clear(int n) {
        fa.resize(n + 1), ssz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int find(int u) {
        if (fa[u] == u) return fa[u];
        return fa[u] = find(fa[u]);
    }
    bool merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu == fv) return false;
        if (ssz[fu] > ssz[fv]) swap(fu, fv);
        fa[fu] = fv, ssz[fv] += ssz[fu];
        return true;
    }
} ufs;
int n, m;
map<int, int> ma;
int pts[50], cnt;
void kruskal() {
    ufs.clear(n);
    sort(graph_k + 1, graph_k + m + 1);
    for (int i = 1; i <= m; i++) {
        int u = graph_k[i].u, v = graph_k[i].v;
        if (!ufs.merge(u, v)) {
            if (!ma[u]) ma[u] = ++cnt, pts[cnt] = u;
            if (!ma[v]) ma[v] = ++cnt, pts[cnt] = v;
            continue;
        }
        addEdge(u, v, graph_k[i].w, tree, hppt, headt);
    }
}
int f[lgsz][sz], dpp, dfn[sz], dep[sz];
ll tdis[sz];
void dfs(int u, int fa, ll w) {
    dfn[u] = ++dpp, f[0][dpp] = fa, dep[u] = dep[fa] + 1, tdis[u] = tdis[fa] + w;
    for (int p = headt[u]; p; p = tree[p].nxt) {
        int v = tree[p].to;
        if (v != fa) dfs(v, u, tree[p].w);
    }
}
int depmin(int u, int v) {
    return dep[u] < dep[v] ? u : v;
}
void init() {
    for (int i = 1; i <= __lg(n); i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            f[i][j] = depmin(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
}
int lca(int u, int v) {
    int du = dfn[u], dv = dfn[v];
    if (du > dv) swap(du, dv);
    int lg = __lg(dv - du);
    return depmin(f[lg][du + 1], f[lg][dv - (1 << lg) + 1]);
}
ll dis[50][sz];
bool vis[sz];
priority_queue<piit, vector<piit>, greater<piit>> pq;
void dijkstra(int s) {
    fill(dis[ma[s]] + 1, dis[ma[s]] + n + 1, inf);
    memset(vis, 0, sizeof vis);
    dis[ma[s]][s] = 0, pq.push(make_pair(dis[ma[s]][s], s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int p = headg[u]; p; p = graph[p].nxt) {
            int v = graph[p].to;
            if (dis[ma[s]][v] > dis[ma[s]][u] + graph[p].w) {
                dis[ma[s]][v] = dis[ma[s]][u] + graph[p].w;
                pq.push(make_pair(dis[ma[s]][v], v));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        graph_k[i] = edge_k{u, v, d};
        addEdge(u, v, d, graph, hppg, headg);
    }
    kruskal();
    dfs(1, 1, 0);
    init();
    for (int i = 1; i <= cnt; i++)
        dijkstra(pts[cnt]);
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        int l = lca(u, v);
        ll ans = inf << 1;
        for (int i = 1; i <= cnt; i++)
            ans = min(ans, dis[i][u] + dis[i][v]);
        cout << min(tdis[u] + tdis[v] - 2 * tdis[l], ans) << endl;
    }
    return 0;
}