Bottleneck Water Pipe Path

A water supply company in MY City needs to deliver water from node u to node v in its aging pipe network. The city’s network is modeled as an undirected graph with n nodes (numbered from 1 to n) and m edges (pipes). Each pipe has a preparation time (for cleaning, disinfection, etc.) that may differ from pipe to pipe. When a delivery task starts, the preparation of all pipes along the selected path is initiated simultaneously; hence, the overall preparation time is determined by the slowest (maximum time) pipe on that path.

The company wants to minimize this overall preparation time. In other words, you need to choose a path from u to v such that the maximum edge weight along the path is as small as possible. Note that due to the old age of the pipes some of them might be out of service; these pipes simply will not be used.

If there is no available path between u and v, output -1. Otherwise, for each delivery task, output the minimum possible overall preparation time.

inputFormat

The first line contains three integers n, m and q, representing the number of nodes, the number of pipes, and the number of delivery tasks, respectively.

Then follow m lines, each containing three integers u, v and w, which indicate that there is an undirected pipe connecting nodes u and v with a preparation time of w.

After that, there are q lines. Each line contains two integers u and v representing a delivery request from node u to node v.

outputFormat

For each of the q queries, output a single line containing one integer: the minimum possible overall preparation time (i.e. the minimum among the maximum pipe preparation times along a valid path). If there is no available path from u to v, output -1.

sample

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

5
5