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