P4197 [ONTAK2010] Peaks

In Bytemountains, there are $n$ peaks, and each peak has its height $h_i$. Some pairs of peaks are connected by bidirectional roads; there are $m$ roads in total. Each road has a difficulty value, and a larger value means it is harder to traverse. There are $q$ queries. For each query, starting from vertex $v$, you may only traverse roads whose difficulty is less than or equal to $x$. Among all peaks reachable this way, find the $k$-th highest peak. If there is no such peak, output $-1$.

The first line contains three integers $n, m, q$. The second line contains $n$ integers, where the $i$-th is $h_i$. The next $m$ lines each contain three integers $a, b, c$, indicating there is a bidirectional road between $a$ and $b$ with difficulty $c$. The next $q$ lines each contain three integers $v, x, k$, describing a query.

For each query, output a single integer: the height of the $k$-th highest reachable peak.

Constraints For $100\%$ of the testdata, $1 \le v, k \le n \le 10^5$, $1 \le m, q \le 5 \times 10^5$, $1 \le h_i, c, x \le 10^9$. Translated by ChatGPT 5