package chelper;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

import io.InputReader;
import io.OutputWriter;
import misc.Pair;
import misc.SimpleSavingChelperSolution;


public class TaskF extends SimpleSavingChelperSolution {

  public static final long INF = Long.MAX_VALUE / 100;
  private Map<Integer, Map<Integer, Long>> edges;
  private int n;
  private int m;
  private int treeCount;
  private int[] vertexTreeId;
  private Set<Integer> treeEgressPointsSet;
  private int[] vertexTreeHeight;
  private long[] vertexTreeLength;
  private boolean[] tainted;
  private int[] dfsIn;
  private int[] dfsOut;
  private int timer;
  private int[][] upside;
  private List<List<Integer>> egressPointsByTree;
  private List<int[]> edges2Dest;
  private List<long[]> edges2Dist;

  public void solve(int testNumber, InputReader in, OutputWriter out) {
    TaskF task = this;

    Thread thread = new Thread(null, new Runnable() {
      @Override
      public void run() {
        task.wrapSolve(testNumber, in, out);
      }
    }, "Test", 1 << 26);
    thread.start();
    try {
      thread.join();
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }

//    wrapSolve(testNumber, in, out);
  }

  static final int UPSIDE_L = 20;

  @Override
  public void solve(int testNumber) {
    long startTime = System.nanoTime();

    n = in.nextInt();
    m = in.nextInt();

    edges = new HashMap<>();
    for (int i = 0; i < n; i++) {
      edges.put(i, new HashMap<>());
    }

    for (int i = 0; i < m; i++) {
      int a = in.nextInt() - 1;
      int b = in.nextInt() - 1;
      long c = in.nextLong();

      edges.get(a).put(b, c);
      edges.get(b).put(a, c);
    }

    treeCount = 0;
    vertexTreeId = new int[n];
    vertexTreeHeight = new int[n];
    vertexTreeLength = new long[n];
    Arrays.fill(vertexTreeId, -1);

    treeEgressPointsSet = new HashSet<>();

    dfsIn = new int[n];
    dfsOut = new int[n];
    timer = 1;

    upside = new int[n][UPSIDE_L + 1];
    for (int i = 0; i < n; i++) {
      Arrays.fill(upside[i], -1);
    }

    tainted = new boolean[n];

    treefy();
//    treefy2();

    debug.println("Treefy finish " + (System.nanoTime() - startTime) / 1e9);
    debug.println("Trees: " + treeCount);
    debug.println("TEP: " + treeEgressPointsSet.size());

    egressPointsByTree = new ArrayList<>();
    for (int i = 0; i < treeCount; i++) {
      egressPointsByTree.add(new ArrayList<>());
    }

    for (int v1 : treeEgressPointsSet) {
      egressPointsByTree.get(vertexTreeId[v1]).add(v1);
    }

    edges2Dest = new ArrayList<>();
    edges2Dist = new ArrayList<>();

    for (int v = 0; v < n; v++) {
      int m = edges.get(v).size();

      int[] dest = new int[m];
      long[] dist = new long[m];
      int k = 0;
      for (Map.Entry<Integer, Long> entry : edges.get(v).entrySet()) {
        int vv = entry.getKey();
        long c = entry.getValue();

        dest[k] = vv;
        dist[k] = c;
        k++;
      }
      edges2Dest.add(dest);
      edges2Dist.add(dist);
    }

    Map<Integer, long[]> egressDistances = new HashMap<>();
    for (int origin : treeEgressPointsSet) {
      long[] distances = new long[n];
      Arrays.fill(distances, INF);
      distances[origin] = 0;

      egressDistances.put(origin, distances);

      egressDijkstra(origin, distances);
    }
    debug.println("Dijkstra finish " + (System.nanoTime() - startTime) / 1e9);

    debug.println("preprocess finish " + (System.nanoTime() - startTime) / 1e9);

    int requestCount = in.nextInt();
    for (int i = 0; i < requestCount; i++) {
      int a = in.nextInt() - 1;
      int b = in.nextInt() - 1;

      long res = INF;

      if (vertexTreeId[a] == vertexTreeId[b]) {
        res = Math.min(res, insideTreeDistance(a, b));
      }

      for (int v1 : egressPointsByTree.get(vertexTreeId[a])) {
        long dist = egressDistances.get(v1)[a] + egressDistances.get(v1)[b];

        res = Math.min(res, dist);
      }

      out.println(res);
    }
  }

  boolean isUpsideInTree(int a, int b) {
    return dfsIn[a] <= dfsIn[b] && dfsOut[a] >= dfsOut[b];
  }

  int lca(int a, int b) {
    if (isUpsideInTree(a, b)) {
      return a;
    }
    if (isUpsideInTree(b, a)) {
      return b;
    }
    for (int l = UPSIDE_L; l >= 0; l--) {
      if (upside[a][l] == -1) {
        continue;
      }
      if (!isUpsideInTree(upside[a][l], b)) {
        a = upside[a][l];
      }
    }
    return upside[a][0];
  }

  long insideTreeDistance(int v1, int v2) {
    int l = lca(v1, v2);

    return vertexTreeLength[v1] + vertexTreeLength[v2] - vertexTreeLength[l] * 2;
  }

  void treefyDfs(int v, List<Integer> stack) {
    dfsIn[v] = timer++;

    for (Map.Entry<Integer, Long> edge : edges.get(v).entrySet()) {
      int vv = edge.getKey();
      long c = edge.getValue();

      if (vertexTreeId[vv] == -1 && !tainted[vv]) {
        for (Map.Entry<Integer, Long> edge2 : edges.get(vv).entrySet()) {
          int vvv = edge2.getKey();

          if (vertexTreeId[vvv] == vertexTreeId[v] && vvv != v) {
            tainted[vv] = true;
          }
        }

        if (tainted[vv]) {
          continue;
        }

        vertexTreeId[vv] = vertexTreeId[v];
        vertexTreeHeight[vv] = vertexTreeHeight[v] + 1;
        vertexTreeLength[vv] = vertexTreeLength[v] + c;

        stack.add(vv);

        for (int l = 0; l <= UPSIDE_L; l++) {
          int j = stack.size() - 1 - (1 << l);
          if (j < 0) {
            break;
          }
          upside[vv][l] = stack.get(j);
        }
        treefyDfs(vv, stack);

        stack.remove(stack.size() - 1);
      }

      if (vertexTreeId[v] != vertexTreeId[vv] && vertexTreeId[vv] != -1) {
        treeEgressPointsSet.add(v);
        treeEgressPointsSet.add(vv);
      }
    }

    dfsOut[v] = timer++;
  }

  void egressDijkstra(int origin, long[] distances) {
    PriorityQueue<long[]> queue = new PriorityQueue<>(new Comparator<long[]>() {
      @Override
      public int compare(long[] o1, long[] o2) {
        return Long.compare(o1[0], o2[0]);
      }
    });
    Arrays.fill(tainted, false);

    int treeId = vertexTreeId[origin];

    queue.add(new long[]{0L, origin});
    tainted[origin] = true;

    while (!queue.isEmpty()) {
      int v = (int) queue.poll()[1];

      int[] dest = edges2Dest.get(v);
      long[] dist = edges2Dist.get(v);

      for (int i = 0; i < dest.length; i++) {
        int vv = dest[i];
        long c = dist[i];

        distances[vv] = Math.min(distances[vv], distances[v] + c);

        if (tainted[vv]) {
          continue;
        }

        tainted[vv] = true;
        queue.add(new long[]{distances[vv], vv});
      }
    }

  }


  void treefy() {
    for (int v = 0; v < n; v++) {
      if (vertexTreeId[v] == -1) {
        Arrays.fill(tainted, false);

        int treeId = treeCount;
        treeCount++;
        vertexTreeId[v] = treeId;
        vertexTreeHeight[v] = 0;
        vertexTreeLength[v] = 0;

        List<Integer> stack = new ArrayList<>();
        stack.add(v);

        treefyDfs(v, stack);
      }
    }
  }
}