Minimum Transportation Costs

You are given an undirected weighted graph with N nodes and M edges. Each edge connects two nodes and has a weight representing the transportation cost between those nodes. You are also given Q queries. Each query consists of two integers representing two nodes, and your task is to determine the minimum transportation cost between these nodes.

If there is no valid path between the queried nodes, output -1. In the case where the query asks for the transportation cost from a node to itself, the answer is 0.

The problem can be formalized as follows:

Given a graph \(G=(V,E)\) where \(V\) is the set of nodes and \(E\) is the set of edges, and each edge \((u,v)\) has a weight \(w_{uv}\), for a given pair of nodes \(s\) and \(t\), find the minimum cost \(d(s,t)\) such that:

[ d(s,t)=\min_{\text{paths } P: s\rightarrow t} \sum_{(u, v) \in P} w_{uv} ]

If no such path exists, output -1.

inputFormat

The input is given from standard input (stdin) and has the following format:

N M Q
u1 v1 w1
u2 v2 w2
... (M lines for edges)
q1 r1
q2 r2
... (Q lines for queries)

Where:

• N is the number of nodes.
• M is the number of edges.
• Q is the number of queries.
• Each of the next M lines contains three integers \(u, v, w\) denoting an undirected edge between nodes u and v with weight w.
• Each of the next Q lines contains two integers representing a query.

outputFormat

For each query, output the minimum transportation cost on a separate line. If there is no path between the two nodes, output -1.

## sample

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

10
4
6

</p>