題意：n個(gè)點(diǎn)的一個(gè)無向圖，在保證存在t條從1到n的不重復(fù)路徑（任意一條邊都不能重復(fù))的前提下，要使得這t條路徑上的最大的那條邊最小。
解法：二分t條路徑上的最大邊權(quán)，對(duì)原圖的每一條邊如果其<=mid,添加一條容量是1的邊（正反都加上），然后跑一遍最大流，如果流量>=t,說明可以安排。迭代得最小值即可。
PS:我一直以為無向圖不能拆成2條相反邊的，但是這個(gè)題用這個(gè)做法卻AC了。由于被那道two shortest題目影響，我覺得是不是也要先求出最短路徑樹然后把dis[i]+w[i][j]>=dis[j]的邊建起來，把無向邊轉(zhuǎn)化成有向邊來做，但是這樣卻wa了，不知道為什么。也許這個(gè)題恰好能拆邊吧。
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;
}