All-Pairs Shortest Paths and Query Processing

This problem requires you to implement the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in an undirected weighted graph. You will be given:

• An integer \(n\) representing the number of vertices.
• An integer \(m\) representing the number of edges.
• An integer \(Q\) representing the number of queries.

Each of the next \(m\) lines contains three integers \(u\), \(v\), \(w\) describing an edge between vertices \(u\) and \(v\) with weight \(w\). Note that the graph is undirected so each edge works in both directions.

After the edges, each of the following \(Q\) lines contains two integers \(a\) and \(b\) for which you must find the shortest path distance from vertex \(a\) to vertex \(b\). If no such path exists, output -1.

Algorithm Note: The Floyd-Warshall algorithm computes the distance matrix \(D\) using the recurrence:

\[ D[i][j] = \min (D[i][j],\; D[i][k] + D[k][j])\quad \text{for all } k \in \{1,\ldots,n\} \]

where initially \(D[i][j]=\infty\) if there is no direct edge between \(i\) and \(j\), and \(0\) if \(i=j\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(Q\) separated by spaces.

The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), representing an edge between vertices \(u\) and \(v\) with weight \(w\).

The following \(Q\) lines each contain two integers \(a\) and \(b\), representing a query to find the shortest path distance between vertices \(a\) and \(b\).

outputFormat

For each query, output a single line containing the shortest path length between the given vertices. If no path exists, output -1.

## sample

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

7
3
5

</p>