#include
#include
#include
using namespace std;
int nump,nume,numr,l=0,r=0;
int dis[201],mapp[201][201],start[40001],endd[40001],val[40001];
inline int minn(int a,int b)
{
return a
bool bfs()
{
int t;
memset(dis,-1,sizeof(dis));
dis[1]=0;
queue
q.push(1);
while(!q.empty())
{
t=q.front();q.pop();
for(int a=0;a<=nump;a++)
{
if(mapp[t][a]>0 && dis[a]<0)
{
dis[a]=dis[t]+1;
q.push(a);
}
}
}
if(dis[nump]>0)
{
return true;
}
else
{
return false;
}
}
int dfs(int from,int restfl)
{
if(from==nump)
{
return restfl;
}
int t;
for(int a=0;a<=nump;a++)
{
if(mapp[from][a]>0 && dis[a]==dis[from]+1 && (t=dfs(a,minn(mapp[from][a],restfl))))
{
mapp[from][a]-=t;
mapp[a][from]+=t;
return t;
}
}
return 0;
}
inline void ins(int st,int ed,int va)
{
mapp[st][ed]=va;
mapp[ed][st]=va;
}
int check(int length)
{
int ttt=0,d=0;
memset(mapp,0,sizeof(mapp));
for(int a=1;a<=nume;a++)
{
if(val[a]<=length)
{
ins(start[a],endd[a],1);
}
}
while(bfs())
{
while(ttt=dfs(1,0x7fffffff))
{
d+=ttt;
}
}
return d;
}
int main()
{
int mid,ans;
cin>>nump>>nume>>numr;
for(int a=1;a<=nume;a++)
{
scanf("%d%d%d",&start[a],&endd[a],&val[a]);
if(r
r=val[a];
}
}
while(l
mid=(l+r)/2;
if(check(mid)>=numr)
{
r=mid-1;
ans=mid;
}
else
{
l=mid+1;
}
}
cout<
}