트럭

Subtle Balloons Company(SBC)는 프로그래밍 대회에 풍선을 공급한다. 큰 공장과 창고를 운영하고, 트럭도 여러 대 보유한다.

Nlogonia에는 대회장이 많고, 모두 SBC에 풍선 배송을 맡겼다. Nlogonia는 여러 개의 다리로 이어진 군도다. 한 섬에 대회장이 여러 곳 있을 수 있고, SBC 창고도 여러 개 있을 수 있다.

배송 경로를 계획하다가 SBC는 문제에 부딪혔다. 안전을 위해 Nlogonia의 모든 다리에는 건너는 차량의 최대 무게 제한이 있다. 실어야 할 화물이 무거워서, SBC 운영 책임자는 창고에서 대회장까지 트럭이 실어 나를 수 있는 최대 무게를 구하는 프로그램을 요청했다.

첫째 줄에 정수 $N$, $M$, $S$가 주어진다. 각각 섬의 수, 섬을 잇는 다리의 수, 대회장의 수다. 섬에는 $1$번부터 $N$번까지 번호가 붙어 있다.

다음 $M$개 줄에는 다리 하나를 나타내는 정수 $A$, $B$, $W$가 주어진다. 앞의 두 수는 그 다리가 잇는 두 섬의 번호이고, $W$는 그 다리의 최대 허용 무게다. 단위는 톤이다.

모든 다리는 양방향으로 통행할 수 있다. 두 섬을 잇는 다리는 많아야 하나다. 다리만 이용해서 어느 섬에서든 다른 모든 섬으로 갈 수 있다. 가는 길에 다른 섬을 거쳐야 할 수도 있다.

다음 $S$개 줄에는 대회장 하나를 나타내는 정수 $L$과 $H$가 주어진다. $L$은 대회장이 있는 섬의 번호이고, $H$는 그 대회장으로 풍선을 배송할 창고가 있는 섬의 번호다.

제한

• $2 \le N \le 2 \times 10^4$
• $1 \le M \le 10^5$
• $1 \le S \le 5 \times 10^4$
• $1 \le A, B, L, H \le N$, $A \ne B$, $L \ne H$
• $0 \le W \le 10^5$

입력에 주어진 순서대로 대회장마다 한 줄에 정수 하나를 출력한다. 창고에서 그 대회장까지 트럭이 실어 나를 수 있는 가장 큰 무게다.

트럭은 섬을 몇 개든 거쳐 갈 수 있다. 한 경로로 실어 나를 수 있는 무게는 그 경로에 있는 다리 제한 중 가장 작은 값이다.