Shortest Path Queries in Directed Graph

You are given a directed graph with n nodes and m edges. Each edge is described by three integers \(u\), \(v\) and \(w\) representing a directed edge from node \(u\) to node \(v\) with weight \(w\) (which can be negative). You are then given \(q\) queries, each consisting of two integers \(s\) and \(t\). For each query, compute the shortest path weight from \(s\) to \(t\). If no path exists, output \(-1\).

Note: The input guarantees that there are no negative cycles in the graph. Use appropriate algorithms to handle negative weights (for example, the Bellman-Ford algorithm).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space.

The next \(m\) lines each contain three integers \(u\), \(v\) and \(w\), representing a directed edge from \(u\) to \(v\) with weight \(w\).

The following line contains an integer \(q\), the number of queries.

Then \(q\) lines follow, each containing two integers \(s\) and \(t\) representing a query to find the shortest path from node \(s\) to node \(t\).

outputFormat

For each query, output a single integer which is the shortest path weight from \(s\) to \(t\). If no path exists, output \(-1\). Each answer should be printed on its own line.

## sample

4 4
1 2 5
2 3 2
3 4 1
1 3 9
2
1 4
2 4

8
3

</p>