这题我没写线段树合并也没写 Kruskal 重构树，而是敲了一个 Splay。

大致思路就是对于每一个点维护一棵 Splay，将询问离线排序后从小到大加边，用启发式合并的方式合并两颗 Splay。

#include<bits/stdc++.h>

#define RI register int

using namespace std;

namespace IO{
    inline int read(){
    	RI X=0, W=0;register char ch=getchar();
    	while(!isdigit(ch)) W|=ch=='-', ch=getchar();
    	while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
    	return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;

const int MAXN = 1e6+5;

int n, m, q;
int fa[MAXN];
int val[MAXN], siz[MAXN];
int ch[MAXN][2];
int root[MAXN];
int cnt[MAXN], sz[MAXN];
int trash[MAXN], tot;
int newnode;
int ans[MAXN];
int cnt_, sq[MAXN];

struct edge{
	int u, v, w;
	bool friend operator < (const edge &x, const edge &y){return x.w<y.w;}
}e[MAXN];

struct query{
	int u, x, k, id;
	bool friend operator < (const query &x, const query &y){return x.x<y.x;}
}ask[MAXN];

inline bool get(int x){return x==ch[fa[x]][1];}

inline void pushup(int x){
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
	return ;
}

inline void rotate(int x){
	int f=fa[x], gf=fa[f], which=get(x), W=ch[x][!which];
	if(gf) ch[gf][get(f)]=x;
	ch[x][!which]=f, ch[f][which]=W;
	if(W) fa[W]=f;
	fa[f]=x, fa[x]=gf;
	pushup(f), pushup(x);
	return ;
}

inline void splay(int p, int x, int goal=0){
	int f;
	while((f=fa[x])!=goal){
		if(fa[f]!=goal) rotate(get(x)==get(f)?f:x);
		rotate(x);
	}
	if(!goal) root[p]=x;
	return ;
}

int f[MAXN];

inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

inline int MakeNewnode(int v){
	int p;
	if(tot) p=trash[tot--];
	else p=++newnode;
	ch[p][0]=ch[p][1]=0;
	fa[p]=0, val[p]=v;
	cnt[p]=siz[p]=1;
	return p;
}

inline void ins(int p, int v){
	int now=root[p], las;
	while(now){
		if(val[now]==v){
			cnt[now]++;siz[now]++;
			return pushup(now), splay(p,now);
		}
		las=now, now=ch[now][val[now]<v];
		if(!now){
			now=MakeNewnode(v);
			fa[now]=las;ch[las][val[las]<v]=now;
			return pushup(las), splay(p,now);
		}
	}
	if(!root[p])
		root[p]=MakeNewnode(v);
}

inline int getans(int v, int x, int k){
	k=siz[x]-k+1;
	while(x){
		if(siz[ch[x][0]]>=k) x=ch[x][0];
		else {
			k-=siz[ch[x][0]];
			if(cnt[x]>=k) return splay(v,x), val[x];
			k-=cnt[x];
			x=ch[x][1];
		}
	}
	return -2333;
}

inline void dfs(int x){
	sq[++cnt_]=val[x];trash[++tot]=x;
	if(ch[x][0]) dfs(ch[x][0]);
	if(ch[x][1]) dfs(ch[x][1]);
	return ;
}

inline void add(int x){
	int xx=e[x].u, yy=e[x].v;
	xx=find(xx), yy=find(yy);
	if(xx==yy) return ;
	if(sz[xx]>sz[yy]) swap(xx,yy);
	if(siz[root[xx]]!=sz[xx]) exit(233);
	cnt_=0;dfs(root[xx]);
	if(cnt_!=sz[xx]) exit(1);//这个地方 dfs 出来的 Splay 大小和并查集大小不符
	for(int i=1;i<=cnt_;++i) ins(yy,sq[i]);
	f[xx]=yy;sz[yy]+=sz[xx];
	return ;
}

int main(){
	n=read(), m=read(), q=read();
	for(int i=1;i<=n;++i) f[i]=i, sz[i]=1, ins(i,read());
	for(int i=1;i<=m;++i) e[i]=edge{read(),read(),read()};
	sort(e+1,e+1+m);
	for(int i=1;i<=q;++i) ask[i]=query{read(),read(),read(),i};
	sort(ask+1,ask+1+q);int now=1;
	for(int i=1;i<=q;++i){
		while(now<=m && e[now].w<=ask[i].x) add(now), now++;
		if(sz[find(ask[i].u)]<ask[i].k) ans[ask[i].id]=-1;
		else ans[ask[i].id]=getans(f[ask[i].u],root[f[ask[i].u]],ask[i].k);
	}
	for(int i=1;i<=q;++i) write(ans[i]), putchar(10);
	return 0;
}