Grand Canal

There are N cities in Korea, and M bidirectional canals will connect them. Each canal has a width w. A ship can pass through a canal only if the ship's width is less than or equal to the canal's width.

The government has planned K shipping routes. Each route connects two cities i and j, and the ship for that route must be able to travel from i to j along some path of canals. If several paths are possible, any one of them may be chosen.

A wider ship can carry more passengers, so for each route, find the maximum possible width of a ship that can operate on that route.

All N cities are guaranteed to be connected by the canals, and every canal can be traveled in both directions.

The first line contains the number of cities N, the number of canals M, and the number of routes K. (N <= 1000, M <= 100000, K <= 10000)

Each of the next M lines contains three integers i, j, and w, meaning that there is a bidirectional canal of width w between city i and city j. (1 <= i, j <= N, w <= 200)

Each of the next K lines contains two cities i and j connected by one route. (1 <= i, j <= N)

Print K lines. For each route in input order, print the maximum width of a ship that can operate on that route.