public static void solve(int nodes, List<List<Integer>> input, int q, List<List<Integer>> queries ) throws IOException {
    
//Using Floyd Warshall algorithm 
//https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
    
    BufferedWriter writer = new BufferedWriter(new PrintWriter(System.out));
    
    int[][] cost = new int[nodes + 1][nodes + 1];
    
//Should have used value > 350, maybe 10000,
//Because Integer.MAX_VALUE < (Integer.MAX_VALUE + int a) 
// because of overflow 
    
    for (int i = 0; i < nodes + 1; i++) {
        for (int j = 0; j < nodes + 1; j++) {
            cost[i][j] = Integer.MAX_VALUE;
            
            if (j == i) {
                cost[i][j] = 0;
            }
            
        }
    }
    
    for (List<Integer> list : input) {
        int startNode = list.get(0);
        int destNode = list.get(1);
        int weight = list.get(2);
        
        cost[startNode][destNode] = weight;
    }
    
    for (int k = 1; k < nodes + 1; k++) {
        for (int i = 1; i < nodes + 1; i++) {
            for (int j = 1; j < nodes + 1; j++) {
                if (cost[i][k] != Integer.MAX_VALUE
                        && cost[k][j] != Integer.MAX_VALUE
                        && cost[i][j] > cost[i][k] + cost[k][j]) {
                    cost[i][j] = cost[i][k] + cost[k][j];
                }
            }
        }
    }
    
    for (List<Integer> query : queries) {
        int startNode = query.get(0);
        int destNode = query.get(1);
        
        int lowestWeight = cost[startNode][destNode];
        
        if (lowestWeight == Integer.MAX_VALUE) lowestWeight = -1;
        
        writer.write(lowestWeight + "\n");
    }
    
    writer.flush();
    writer.close();
}






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<List<Integer>> input = new ArrayList<>();      

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

            List<Integer> list = new ArrayList<>();
            
            list.add(Integer.parseInt(roadFromToWeight[0]));
            list.add(Integer.parseInt(roadFromToWeight[1]));
            list.add(Integer.parseInt(roadFromToWeight[2]));
            
            input.add(list);
            
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
    });

    int q = Integer.parseInt(bufferedReader.readLine().trim());
    
    List<List<Integer>> queries = new ArrayList<>();

    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> query = new ArrayList<>();
            
            query.add(x);
            query.add(y);
            
            queries.add(query);
            
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
    });
    

    solve(roadNodes, input, q, queries);
    
    bufferedReader.close();
}