Imperial Roads

#include <bits/stdc++.h>

using namespace std;

#define topper top //XDDDDDDD

#define mp make_pair
#define pb push_back
#define db(x) cerr << #x << " == " <<  x << endl;
#define _ << " " <<

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

const long double EPS = 1e-9;
const int N=1e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int n, r, ans;
ll cost;
int par[N], sz[N], sp[30][N], m[30][N], h[N];
vector<int> adj[N];
vector<pair<int, pair<int, int>>> ed;
map<ii, int> wt;

int find(int i) { return i == par[i] ? i : par[i] = find(par[i]); }

void unite(int a, int b) {
  if((a = find(a)) == (b = find(b))) return;

  if(sz[a] > sz[b]) swap(a, b);
  par[a] = b; sz[b] += sz[a];
}

ll mst() {
  for(int i=1; i<=n; i++) adj[i].clear();

  sort(ed.begin(), ed.end());

  ll res = 0;
  for(auto i : ed) {
    int u = i.second.first, v = i.second.second;
    if(find(u) != find(v)) {
      unite(u, v);
      res += i.first;
      adj[u].pb(v), adj[v].pb(u);
    }
  }
  return res;
}

void dfs(int u) {
  for(int v : adj[u]) {
    if(!h[v]) {
      h[v] = h[u] + 1;
      sp[0][v] = u;
      m[0][v] = wt[mp(u,v)];
      //db(v _ u _ h[v] _ adj[u].size());
      dfs(v);
    }
  }
}

int go(int j, int d) {
  for(int i=19; i>=0; i--) if((1<<i) & d) {
    ans = max(ans, m[i][j]);
    j = sp[i][j];
  }
  return j;
}

int lca(int a, int b) {
  if(h[a] > h[b]) swap(a, b);

  //printf("lca of %d %d: ", a, b);

  ans = 0;

  b = go(b, h[b] - h[a]);

  if(b == a) return ans;

  for(int i=19; i>0; i--) if(sp[i][a] != sp[i][b]) {
   ans = max(ans, m[i][a]); ans = max(ans, m[i][b]);
    a = sp[i][a]; b = sp[i][b];
  }

  ans = max(ans, m[0][a]); ans = max(ans, m[0][b]);
  a = sp[0][a], b = sp[0][b];

  //printf("%d\n", ans);
  return ans;
}

int main(){
  srand(time(0));

  while(scanf("%d %d", &n, &r) != EOF) {
    memset(m, 0, sizeof m);
    memset(par, 0, sizeof par);
    memset(h, 0, sizeof h);
    memset(sz, 0, sizeof sz);
    memset(sp, 0, sizeof sp);

    wt.clear(); ed.clear();

    for(int i=0; i<r; i++) {
      int u, v, c;
      scanf("%d %d %d", &u, &v, &c);

      ed.pb(mp(c, mp(u,v))), ed.pb(mp(c, mp(v,u)));
      wt[mp(u,v)] = wt[mp(v,u)] = c;
    }

    for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1;

    //printf("mst...\n");
    cost = mst();

    int root = 1 + rand() % n;
    h[root] = 1;
    //printf("cost: %lld\n", cost);
    //printf("dfs...\n");
    dfs(root);

    //printf("first step of sparse table...\n");
    for(int i=0; i<20; i++) sp[i][0] = 0;
    sp[0][1] = 0;

    //printf("second step of sparse table...\n");
    for(int i=1; i<20; i++) {
      for(int j=1; j<=n; j++) {
        sp[i][j] = sp[i-1][sp[i-1][j]];
        m[i][j] = max(m[i-1][sp[i-1][j]], m[i-1][j]);
      }
    }

    int q;
    scanf("%d", &q);
    for(int i=0; i<q; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      printf("%lld\n", cost + wt[mp(u,v)] - lca(u,v));
    }
  }

  return 0;
}