Shortest Path Queries using Dijkstra's Algorithm

Given an undirected weighted graph with \( n \) cities and \( m \) roads, each road connects two cities with a positive travel cost. For each query, compute the shortest travel cost from city \( a \) to city \( b \). If there is no path, output \(-1\). The shortest path cost is defined as:

\( d(u,v)=\min_{\text{path}}\sum_{road\in\text{path}} w_{road} \)

You are required to solve this problem using Dijkstra's algorithm.

inputFormat

The input is given via standard input with the following format:

1. The first line contains two integers \( n \) and \( m \), representing the number of cities and roads.
2. Each of the next \( m \) lines contains three integers \( u \), \( v \), and \( w \), where \( u \) and \( v \) are the connected cities and \( w \) is the travel cost.
3. The next line contains an integer \( q \), the number of queries.
4. Each of the following \( q \) lines contains two integers \( a \) and \( b \), representing a query to compute the shortest travel cost from city \( a \) to city \( b \).

outputFormat

For each query, output the shortest travel cost on a separate line. If no path exists, output \(-1\).

## sample

6 9
1 2 4
1 3 2
2 3 5
2 4 10
3 4 3
3 5 8
4 5 5
4 6 6
5 6 1
3
1 6
2 5
3 4

11
13
3

</p>