int l = ed[i].l ;
if(deep[e] == -1 && l > 0 )
{
deep[e] = deep[tt] + 1 ;
qe[h ++ ] = e ;
}
}
}
return deep[T] != -1 ;
}
int dinic_dfs(int now ,int f )
{
if(now == T)return f ;
int flow = 0 ;
for (int i = head[now] ; ~i ; i = ed[i].next )
{
int e = ed[i].e ;
int l = ed[i].l ;
if(deep[e] == deep[now] + 1 && l > 0 && (f - flow))//f - flow > 0 加了这个优化就A了。否则T到死
{
int mm = min(l,f - flow) ;
int nn = dinic_dfs(e , mm) ;
flow += nn ;
ed[i].l -= nn ;
ed[i ^ 1].l += nn ;
}
}
if(!flow )deep[now] = -2 ;
return flow ;
}
int dinic()
{
int flow = 0 ;
int f ;
while(dinic_bfs())
{
flow += dinic_dfs(S,inf) ;
}
return flow ;
}
void build_Map(int mid)
{
init() ;
for (int i = 1 ; i <= C ; i ++ )
{
if(e[i].l <= mid)
{
add(e[i].s ,e[i].e ,1) ;
add(e[i].e ,e[i].s ,1) ;
}
}
add(S,1,inf) ;
add(N,T,inf) ;
}
int main()
{
scanf("%d%d%d",&N,&C,&M) ;
int l = inf ,r = -1 ;
S = 0 ,T = N + 1 ;
for (int i = 1 ; i <= C ; i ++ )
{
scanf("%d%d%d",&e[i].s,&e[i].e,&e[i].l) ;
l = min(l,e[i].l) ;
r = max(r,e[i].l) ;
}
int mid = l + r >> 1 ;
while(r > l)
{
mid = (l + r ) >> 1 ;
build_Map(mid) ;
int ans = dinic() ;
if(ans < M) l = mid + 1 ;
else r = mid ;
}
printf("%d\n",r) ;
return 0;
}