题意：n个点的一个无向图，在保证存在t条从1到n的不重复路径（任意一条边都不能重复)的前提下，要使得这t条路径上的最大的那条边最小。
解法：二分t条路径上的最大边权，对原图的每一条边如果其<=mid,添加一条容量是1的边（正反都加上），然后跑一遍最大流，如果流量>=t,说明可以安排。迭代得最小值即可。
PS:我一直以为无向图不能拆成2条相反边的，但是这个题用这个做法却AC了。由于被那道two shortest题目影响，我觉得是不是也要先求出最短路径树然后把dis[i]+w[i][j]>=dis[j]的边建起来，把无向边转化成有向边来做，但是这样却wa了，不知道为什么。也许这个题恰好能拆边吧。
PSS:这题卡sap,用dinic才过掉
int mat[maxn][maxn];
int n,m,t;
struct node2
{
int a,b,c;
}ee[40010];
void input()
{
//scanf("%d%d%d",&n,&m,&t);
/**//*
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)mat[i][j]=0;
else mat[i][j]=INF;
}
*/
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a--;b--;
ee[i].a=a;ee[i].b=b;ee[i].c=c;
/**//* if(c<mat[a][b])
mat[a][b]=mat[b][a]=c;
*/
}
}
/**//*
int dis[maxn];
int use[maxn];
void SPFA(int n,int s)
{
fill(dis,dis+n,INF);
fill(use,use+n,0);
dis[s]=0;
use[s]=1;
queue<int>Q;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();Q.pop();
use[x]=0;
for(int i=0;i<n;i++)
{
if(dis[x]+mat[x][i]<dis[i])
{
dis[i]=dis[x]+mat[x][i];
if(!use[i])
{
use[i]=1;
Q.push(i);
}
}
}
}
}
*/
bool check(int mid)
{
for(int i=0;i<n;i++)
adj[i]=NULL;
len=0;
for(int i=0;i<m;i++)
{
int a=ee[i].a;
int b=ee[i].b;
/**//*
if(dis[a]+ee[i].c>=dis[b]&&ee[i].c<=mid)
insert(a,b,1);
else if(dis[b]+ee[i].c>=dis[a]&&ee[i].c<=mid)
insert(b,a,1);
*/
if(ee[i].c<=mid)
{
insert(a,b,1);
insert(b,a,1);
}
}
return dinic(n,0,n-1)>=t;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
input();
//SPFA(n,0);
int l=0;
int r=1000000;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d\n",ans);
return 0;
}