소 허들 넘기

농부 존은 소들이 카운티 점프 대회를 준비하도록 하고 싶어 합니다. 그래서 베시와 친구들은 허들을 넘는 연습을 하고 있습니다. 하지만 점점 지쳐서, 허들을 넘을 때 가능한 한 적은 힘을 쓰고 싶어 합니다.

낮은 허들 여러 개를 넘는 것은 소에게 그리 어렵지 않지만, 아주 높은 허들 하나는 큰 부담이 됩니다. 그래서 소들은 자신이 넘어야 하는 허들 중 가장 높은 허들의 높이에만 신경을 씁니다.

연습장에는 $N$개의 지점이 있으며 $1 \ldots N$으로 번호가 매겨져 있습니다 ($1 \le N \le 300$). $M$개의 단방향 경로가 지점 쌍을 연결하고, 경로에도 $1 \ldots M$으로 번호가 매겨져 있습니다 ($1 \le M \le 25{,}000$). 경로 $i$는 지점 $S_i$에서 지점 $E_i$로 향하며, 높이가 $H_i$인 허들이 정확히 하나 있습니다 ($1 \le H_i \le 1{,}000{,}000$). 소는 자신이 지나가는 모든 경로의 허들을 반드시 넘어야 합니다.

소들에게는 완료해야 할 $T$개의 작업이 있습니다 ($1 \le T \le 40{,}000$). 작업 $i$는 서로 다른 두 수 $A_i$와 $B_i$로 이루어지며 ($1 \le A_i \le N$, $1 \le B_i \le N$), 소가 하나 이상의 경로를 지나 지점 $A_i$에서 지점 $B_i$까지 이동해야 함을 뜻합니다. 소는 $A_i$에서 $B_i$로 이동하면서 넘어야 하는 가장 높은 허들의 높이를 최소화하는 경로로 이동하고 싶어 합니다. 각 작업에 대해, 넘어야 하는 가장 높은 허들의 높이가 가장 작아지는 경로를 찾아 그 높이를 출력하는 프로그램을 작성하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $T$
• 둘째 줄부터 $M+1$번째 줄까지: $i+1$번째 줄에는 공백으로 구분된 세 정수 $S_i$, $E_i$, $H_i$가 주어집니다.
• $M+2$번째 줄부터 $M+T+1$번째 줄까지: $i+M+1$번째 줄에는 작업 $i$를 설명하는 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어집니다.

• 첫째 줄부터 $T$번째 줄까지: $i$번째 줄에 작업 $i$의 결과, 즉 두 지점 사이를 이동할 때 필요한 가장 높은 허들 높이의 최솟값을 출력합니다. 두 지점 사이를 이동하는 것이 불가능하면 $-1$을 출력합니다.