10821082 SUSTech Online Judge
Problem 1082 --The cheapest path

## 1082: The cheapest path

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 121  Solved: 21
[Submit][Status][Web Board]

## Description

There are n cities and m roads. Each road is bidirectional. When we go from city x to city y, we have to go through some roads. Each road has a cost. We define the cheapest path between city x and y if and only if the most expensive cost from city x to y is cheapest. Now we have q queries. Each query has two integers x y. It means we want to find the cheapest path from x to y. Please print the cost in this cheapest path. If we cannot go to y from x, print -1.

Note: There may be multiple roads between two cities.

## Input

The first line will be an integer T. (1 <= T <= 5) T is the number of test cases.

For each test case, the first line will be three integers n, m and q. (1 <= n <= 5000, 1 <= m <= 100000, 1 <= q <= 5000)

Then there will be m lines. Each line contains three integers u v w. Means there is a road from u to v. And the cost of this road is w. (1 <= u, v <= n, 1 <= w <= 105)

Then there will be q lines. Each line contains two integers u v. Means we want to find the value from u to v.

## Output

For each query, print the value the problem required.

## Sample Input

1
8 8 4
1 2 1
1 3 7
1 4 6
4 6 2
6 5 4
2 5 7
6 7 3
7 8 5
1 5
1 3
6 2
4 8


## Sample Output

6
7
6
5


## HINT

For 1 5, we go through 1->4->6->5,
the most expensive cost is 6.

[Submit][Status]