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
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.
For each query, print the value the problem
For 1 5, we go through 1->4->6->5,
the most expensive cost is 6.