![](https://cdn.luogu.com.cn/upload/pic/40868.png)
by 许凉城 @ 2018-10-30 20:05:57
已过,感谢题解的大佬,仿佛打开了新世界的大门/笑哭
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,x[100005],y[100005],t[100005],p,q,f[100005];
bool flag;
int find(int x)
{
if (f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void qsort(int l,int r)
{
int i=l,j=r,mid=t[(i+j)/2];
while (i<=j)
{
while (t[i]<mid) i++;
while (t[j]>mid) j--;
if (i<=j)
{
swap(x[i],x[j]);
swap(y[i],y[j]);
swap(t[i],t[j]);
i++;
j--;
}
}
if (l<j) qsort(l,j);
if (i<r) qsort(i,r);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
f[i]=i;
for (int i=1;i<=m;i++)
scanf("%d%d%d",&x[i],&y[i],&t[i]);
qsort(1,m);
for (int i=1;i<=m;i++)
{
p=find(x[i]);
q=find(y[i]);
if (p!=q)
f[q]=p;
flag=true;
for (int j=1;j<=n/2+1;j++)
if (j<n-j+1)
if (find(j)!=find(n-j+1))
{
flag=false;
break;
}
if (flag==true)
{
printf("%d",t[i]);
return 0;
}
}
printf("-1");
return 0;
}
```
by 许凉城 @ 2018-10-30 20:27:44