#!/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)