```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5, MAX_N = N + 3;
const int M = 5e5, MAX_M = M + 3;
int n, m, q, a [MAX_N];
int tot, b [MAX_N];
void init () {
sort (b + 1, b + n + 1);
tot = unique (b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i)
a [i] = lower_bound (b + 1, b + n + 1, a [i]) - b;
}
struct edge {
int u, v, w;
bool operator < (edge _) {return w < _.w;}
} e [MAX_M];
namespace KRUSKAL {
const int log_N = 18, MAX_log_N = log_N + 3;
int root_cnt = 0, now = 0;
int root [MAX_N];
struct node {int val, lc, rc;} t [MAX_N << 5];
#define mid (l + r >> 1)
int anc [MAX_N << 1] [MAX_log_N];
int rt [MAX_N << 1];
int val [MAX_N << 1];
int rge [MAX_N << 1] [2];
int lc [MAX_N << 1], rc [MAX_N << 1];
void insert (int _x, int &x, int l, int r, int val) {
x = ++now;
t [x] = t [_x];
++t [x].val;
if (l == r) return;
if (val <= mid) insert (t [_x].lc, t [x].lc, l, mid, val);
else insert (t [_x].rc, t [x].rc, mid + 1, r, val);
}
int query (int _x, int x, int l, int r, int kth) {
if (l == r) return l;
int s = t [t [x].rc].val - t [t [_x].rc].val;
if (kth <= s) return query (t [_x].rc, t [x].rc, mid + 1, r, kth);
return query (t [_x].lc, t [x].lc, l, mid, kth - s);
}
void dfs (int u) {
for (int i = 1; anc [u] [i - 1]; ++i)
anc [u] [i] = anc [anc [u] [i - 1]] [i - 1];
if (!lc [u] && !rc [u]) {
++root_cnt;
insert (root [root_cnt - 1], root [root_cnt], 1, tot, a [u]);
rge [u] [0] = rge [u] [1] = root_cnt;
return;
}
dfs (lc [u]);
dfs (rc [u]);
rge [u] [0] = rge [lc [u]] [0];
rge [u] [1] = rge [rc [u]] [1];
}
int find (int u) {return u == rt [u] ? u : rt [u] = find (rt [u]);}
void Kruskal () {
int cnt = n;
for (int i = 1; i < 2 * n; ++i) rt [i] = i;
sort (e + 1, e + m + 1);
for (int i = 1; i <= m; ++i) {
int u = find (e [i].u);
int v = find (e [i].v);
if (u ^ v) {
rt [u] = rt [v] = anc [u] [0] = anc [v] [0] = ++cnt;
val [cnt] = e [i].w;
lc [cnt] = u;
rc [cnt] = v;
}
}
for (int u = 1; u < 2 * n; ++u)
if (rt [u] == u) dfs (u);
}
} using namespace KRUSKAL;
signed main () {
scanf ("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; ++i)
scanf ("%d", a + i), b [i] = a [i];
for (int i = 1; i <= m; ++i)
scanf ("%d%d%d", &e [i].u, &e [i].v, &e [i].w);
init ();
Kruskal ();
while (q--) {
static int u, x, k;
scanf ("%d%d%d", &u, &x, &k);
for (int i = log_N; ~i; --i)
if (anc [u] [i] && val [anc [u] [i]] <= x)
u = anc [u] [i];
if (0 < k && k <= rge [u] [1] - rge [u] [0] + 1)
printf ("%d\n", b [query (root [rge [u] [0] - 1], root [rge [u] [1]], 1, tot, k)]);
else puts ("-1");
}
}
```
by George_Je @ 2022-10-09 16:57:54