All-Pairs Shortest Paths

Hard#graphs #floyd-warshall #shortest-path· solved by 0 · time limit 2.0 s

A directed graph has $n \le 300$ nodes and weighted edges. Answer $q$ queries: the shortest distance from $a$ to $b$ , or -1. With so few nodes, Floyd–Warshall ( $O(n^3)$ ) precomputes every answer.

Input

$n$ and $m$ , $m$ lines u v w (directed, there may be repeats), $q$ , then $q$ lines a b.

Output

One answer per line.

Constraints

$1 \le n \le 300$ , $1 \le w \le 10^4$

Sample 1

Input

Output

5
-1
0