Floyd–Warshall: All-Pairs Shortest Paths with Queries

This problem requires you to compute the shortest paths between every pair of nodes in an undirected weighted graph using the Floyd–Warshall algorithm. You are given a graph with n nodes and m edges, and then q queries. Each edge is specified by two endpoints and a latency. For each query, you must determine the minimum latency between the given nodes. If no path exists between a given pair of nodes, output -1.

The recurrence used in the Floyd–Warshall algorithm is given by $$ dist[i][j] = \min(dist[i][j],\; dist[i][k] + dist[k][j]) $$ for every intermediate node k and for all pairs of nodes i and j.

inputFormat

The first line contains three integers n, m, and q — representing the number of nodes, the number of edges, and the number of queries respectively.

The next m lines each contain three integers u, v, and l, denoting that there is an undirected edge between nodes u and v with a latency of l.

The following q lines each contain two integers a and b, indicating a query to determine the shortest latency between nodes a and b.

outputFormat

For each query, output one integer on a new line — the minimum latency between the queried nodes. If there is no path between them, output -1.

## sample

4 4 3
1 2 3
1 3 1
2 3 7
3 4 2
1 2
1 4
2 4

3
3
6

</p>