Cow Hurdles

Farmer John wants the cows to prepare for the county jumping competition, so Bessie and the gang are practicing jumping over hurdles. They are getting tired, though, so they want to use as little energy as possible to clear the hurdles.

Jumping over several short hurdles is not very hard for a cow, but a single tall hurdle can be very stressful. Therefore the cows only care about the height of the tallest hurdle they have to jump over.

The practice room has $N$ stations, labeled $1 \ldots N$ ($1 \le N \le 300$). A set of $M$ one-way paths connects pairs of stations, and the paths are labeled $1 \ldots M$ ($1 \le M \le 25{,}000$). Path $i$ runs from station $S_i$ to station $E_i$ and contains exactly one hurdle of height $H_i$ ($1 \le H_i \le 1{,}000{,}000$). A cow must jump every hurdle on any path it traverses.

The cows have $T$ tasks to complete ($1 \le T \le 40{,}000$). Task $i$ consists of two distinct numbers $A_i$ and $B_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$), meaning a cow must travel from station $A_i$ to station $B_i$ over one or more paths along some route. For each task the cows want a route that minimizes the height of the tallest hurdle they jump over while traveling from $A_i$ to $B_i$. For every task, determine the route whose tallest hurdle is smallest and report that height.

• Line 1: Three space-separated integers: $N$, $M$, and $T$
• Lines $2 \ldots M+1$: Line $i+1$ contains three space-separated integers: $S_i$, $E_i$, and $H_i$
• Lines $M+2 \ldots M+T+1$: Line $i+M+1$ contains two space-separated integers describing task $i$: $A_i$ and $B_i$

• Lines $1 \ldots T$: Line $i$ contains the result for task $i$: the smallest possible maximum hurdle height needed to travel between the two stations. Output $-1$ if it is impossible to travel between them.