记录编号	568441	评测结果	AAAAAAAAAA
题目名称	[USACO20 Jan Silver]虫洞排序	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2022-01-04 19:59:11	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
char ra;
//ll rp;
inline void read(int &x)
{
	x&=0;
//	rp=1;
	ra=getchar();
	while(ra<'0'||ra>'9') 
	{
//		if(ra=='-') rp=-1;
		ra=getchar();
	}
	while(ra>='0'&&ra<='9') 
	{
		x=(x<<3)+(x<<1)+(ra^48);
		ra=getchar();
	}
//	x*=rp;
} 
inline void write(int x)
{
	if(x/10) write(x/10);
	putchar(x%10+48);
}
///////////
const int N=1e5+50;
int nc,mc;
int n[N];
int nj;
int ans;
struct edge
{
	int bg;
	int ed;
	int p;
}a[N];
bool cmp(edge x,edge y){return x.p>y.p;}
int f[N];
int find(int x)
{
	if(x!=f[x])
	{
		f[x]=find(f[x]);
		return f[x];
	}
	return x;
}
int main()
{
	freopen("usaco_Jan_wormsort.in","r",stdin);
	freopen("usaco_Jan_wormsort.out","w",stdout);
    read(nc);
    read(mc);
    int pr=0;
    for(int i=1;i<=nc;i++)
    {
    	read(n[i]);
    	if(n[i]!=i)
    	{
    		pr|=1;
    		n[i]=1;
    		nj++;
		}
		else n[i]=0;
	}
	if(!pr)
	{
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=nc;i++) f[i]=i;
	for(int i=1;i<=mc;i++)
	{
		read(a[i].bg);
		read(a[i].ed);
		read(a[i].p);
		if(a[i].bg>a[i].ed) swap(a[i].bg,a[i].ed);
	}
	sort(a+1,a+1+mc,cmp);
	int s1,s2;
	for(int i=1;i<=mc;i++)
	{
		s1=find(a[i].bg);
		s2=find(a[i].ed);
		if(s1!=s2)
		{
			f[s2]=s1;
			n[s1]+=n[s2];
			if(n[s1]==nj)
			{
				ans=a[i].p;
				break;
			}
		}
	}
	write(ans);
	putchar(10);
	return 0;
}