import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;


public class Solution {
    static PriorityQueue<Node> nodesToVisit = new PriorityQueue<>();
    
    static class Node implements Comparable<Node> {
        int vertex;
        int distance = 0;
        boolean visited = false;

        public Node(int vertex, int distance) {
            // vertexes.
            this.vertex = vertex;
            this.distance = distance;
        }
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Node node = (Node) obj;
            return vertex == node.vertex;
        }
        @Override
        public int hashCode() {
            return Objects.hash(vertex);
        }
        @Override
        public String toString() {
            return "{ Node : "+vertex+" Distance is: "+distance+" }";
        }
    }
    static HashMap<List<Integer>, Integer> results = new HashMap<>();
    static  HashMap<Integer,HashMap<Integer,Integer>> adjacencyList2 = new HashMap<>();
    static HashSet<Integer> visited;

    public static int shortestPathFinder(int sourceVertex, int destination ){
        int weight=0;// weight of current node
        if(sourceVertex == destination) return distance.get(sourceVertex);
        if (!visited.contains(sourceVertex))         
        {   
            weight = distance.get(sourceVertex); // weight of the source

            for (Map.Entry<Integer,Integer> edgeWithWeight : adjacencyList2.get(sourceVertex).entrySet()) {
            //key is edge(neighbour) of source and value is the weight of the edge
            // updating distances to all neighbours
                weight += edgeWithWeight.getValue(); // weight of negihbour edge 
                
                int neighbourExistingWeight = 300000;
                if (distance.containsKey(edgeWithWeight.getKey())) neighbourExistingWeight = distance.get(edgeWithWeight.getKey());

                if (neighbourExistingWeight > weight) { // neighrbour ka existing weight check
                    distance.put(edgeWithWeight.getKey(),weight);
                    Node node = new Node(edgeWithWeight.getKey(), distance.get(edgeWithWeight.getKey()));
                    // if (nodesToVisit.contains(node)) {
                        // nodesToVisit.remove(node);
                    // }
                    nodesToVisit.add(node);  
                }
                weight = distance.get(sourceVertex); // weight of the source

            }
        }
        visited.add(sourceVertex);
        if (nodesToVisit.isEmpty()) return -1;

        return shortestPathFinder(nodesToVisit.remove().vertex, destination);
    }
    
    
    static HashMap<Integer, Integer> distance = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] roadNodesEdges = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int roadNodes = Integer.parseInt(roadNodesEdges[0]);
        int roadEdges = Integer.parseInt(roadNodesEdges[1]);

        // List<Integer> roadFrom = new ArrayList<>();
        // List<Integer> roadTo = new ArrayList<>();
        // List<Integer> roadWeight = new ArrayList<>();

        // int startNode, endNode, weight;
        IntStream.range(0, roadEdges).forEach(i -> {
            try {
                String[] roadFromToWeight = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                // roadFrom.add(Integer.parseInt(roadFromToWeight[0]));
                // roadTo.add(Integer.parseInt(roadFromToWeight[1]));
                // roadWeight.add(Integer.parseInt(roadFromToWeight[2]));
                int startNode = Integer.parseInt(roadFromToWeight[0]);
                int endNode = Integer.parseInt(roadFromToWeight[1]);
                int weight = Integer.parseInt(roadFromToWeight[2]);
       
                HashMap<Integer,Integer> edgesAndWeight = new HashMap<>();
                edgesAndWeight.put(endNode, weight);
                if (adjacencyList2.containsKey(startNode)) {
                    edgesAndWeight = adjacencyList2.get(startNode);
                    edgesAndWeight.put(endNode, weight);
                                
                }else{
                    adjacencyList2.put(startNode, edgesAndWeight);
                }
                if (!adjacencyList2.containsKey(endNode)) {              
                    adjacencyList2.put(endNode, new HashMap<>());
                }
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });
        // System.out.println(adjacencyList2);
        int q = Integer.parseInt(bufferedReader.readLine().trim());

        HashMap<List<Integer>, Integer> results = new HashMap<>(); 
        IntStream.range(0, q).forEach(qItr -> {
            try 
            {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int x = Integer.parseInt(firstMultipleInput[0]);

                int y = Integer.parseInt(firstMultipleInput[1]);
                List<Integer> k = new ArrayList<Integer>(); // query pair
                k.add(x);
                k.add(y);
                int startNode = x;
                int endNode = y;
                int shortestPath = -1;
                if (results.containsKey(k)) {
                    System.out.println(results.get(k));
                }else 
                if(startNode == endNode) System.out.println(0);
                else{
                 
                    visited = new HashSet<>();
                    distance.clear();
                    nodesToVisit.clear();
                    //above is to clear any useless data and start new for new query
                    distance.put(startNode,0);
                    shortestPath = shortestPathFinder(startNode,endNode);
                    System.out.println(shortestPath);
                    results.put(k, shortestPath);
                }
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });
        bufferedReader.close();
    }
}

import itertools as ittls


if __name__ == '__main__':
    road_nodes, road_edges = map(int, input().rstrip().split())

    # road_from = [0] * road_edges
    # road_to = [0] * road_edges
    # road_weight = [0] * road_edges

    adjM=[[math.inf]* road_nodes for _ in range(road_nodes)]
    
    for i in range(road_nodes):
        adjM[i][i]=0
    
    for i in range(road_edges):
        road_from, road_to, road_weight= map(int, input().rstrip().split())
        adjM[road_from-1][road_to-1]=road_weight
        
    for k, j, i in ittls.permutations(range(road_nodes),3):
        if adjM[i][j]>adjM[i][k]+adjM[k][j]:
            adjM[i][j]=adjM[i][k]+adjM[k][j]

        
    

    q = int(input().strip())
    
    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()

        x = int(first_multiple_input[0])-1

        y = int(first_multiple_input[1])-1
        a=adjM[x][y]
        
        if a == math.inf:
            print(-1)
        else:
            print(a)

function shortestPath(n, edges, queries) {
    // Straightforward Floyd-Warshall Algorithm:
    const vertices = new Set()
    const dist = Array(n+1).fill(0).map(v => Array(n+1).fill(Infinity))
    
    edges.forEach(([u, v, w]) => (vertices.add(u).add(v), dist[u][v] = w))
    vertices.forEach(v => (dist[v][v] = 0))
    
    for (let k = 1; k <= n; k++) 
        for (let i = 1; i <= n; i++) 
            for (let j = 1; j <= n; j++)
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])
                
    for (const [u, v] of queries)
        console.log(dist[u][v] === Infinity ? -1 : dist[u][v])
}

function main() {
    const roadNodesEdges = readLine().split(' ');
    const roadNodes = parseInt(roadNodesEdges[0], 10);
    const roadEdges = parseInt(roadNodesEdges[1], 10);
    let edges = [];
    let queries = [];

    for (let i = 0; i < roadEdges; i++) {
        const roadFromToWeight = readLine().split(' ');
        let roadFrom = parseInt(roadFromToWeight[0], 10);
        let roadTo =  parseInt(roadFromToWeight[1], 10);
        let roadWeight = parseInt(roadFromToWeight[2], 10);
        edges.push([roadFrom, roadTo, roadWeight])
    }

    const q = parseInt(readLine().trim(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
        const x = parseInt(firstMultipleInput[0], 10);
        const y = parseInt(firstMultipleInput[1], 10);
        queries.push([x, y]);
    }
    
    shortestPath(roadNodes, edges, queries);
    
}