dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
or
if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

                if dist[i][j] > dist[i][k] + dist[k][j]: 
                    dist[i][j] = dist[i][k] + dist[k][j]

function shortestPath(roadNodes, edges, queries) {
    let matrix = Array(roadNodes);
    for (let i = 0; i < roadNodes; i++) {
        matrix[i] = Array(roadNodes)
        for (let j = 0; j < roadNodes; j++) {
            if (j === i) {
                matrix[i][j] = 0;
                continue;
            }
            matrix[i][j] = Number.MAX_SAFE_INTEGER;
        }
    }
    
    for (const edge of edges) {
        matrix[edge[0]-1][edge[1]-1] = edge[2];
    }
    
    for (let i = 0; i < roadNodes; i++) {
        for (let j = 0; j < roadNodes; j++) {
            for (let k = 0; k < roadNodes; k++) {
                let op = matrix[j][i] + matrix[i][k];
                matrix[j][k] = Math.min(matrix[j][k], op)
            }
        }
    }
    
    for (const query of queries) {
        console.log(matrix[query[0]-1][query[1]-1] !== Number.MAX_SAFE_INTEGER ? matrix[query[0]-1][query[1]-1] : -1)
    }
}

def floyd(road_nodes, road_edges, road_from, road_to, road_weight, queries):
    dist = [[math.inf for _ in range(road_nodes+1)] for _ in range(road_nodes+1)]
    for i in range(road_edges):
        dist[road_from[i]][road_to[i]] = road_weight[i]
    for i in range(road_nodes+1):
        dist[i][i] = 0
    
    for k in range(road_nodes+1):
        for i in range(road_nodes+1):
            for j in range(road_nodes+1):
                if dist[i][j] > dist[i][k] + dist[k][j]: 
                    dist[i][j] = dist[i][k] + dist[k][j]
                    
    for q in queries:
        if dist[q[0]][q[1]] == math.inf:
            print(-1)
        else:
            print(dist[q[0]][q[1]])
        
                    

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

    for i in range(road_edges):
        road_from[i], road_to[i], road_weight[i] = map(int, input().rstrip().split())

    q = int(input().strip())

    queries = []
    
    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()

        x = int(first_multiple_input[0])

        y = int(first_multiple_input[1])
        
        queries.append([x, y])
        
    floyd(road_nodes, road_edges, road_from, road_to, road_weight, queries)

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();
}

#!/bin/python3

import math
import os
import random
import re
import sys

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)