// bzoj1570#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf (1ll<<30)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=1000010;int head[maxn],n,m,T,et,ans,cnt=1;struct data {int u,v,w;}t[maxn];struct edge {int to,next,w;}e[maxn];void link(int u,int v,int w) {	e[++cnt]=(edge){v,head[u],w};head[u]=cnt;	e[++cnt]=(edge){u,head[v],0};head[v]=cnt;}namespace Dinic {	int d[maxn],s,t;	bool bfs(int s,int t) {		memset(d,-1,sizeof(d));		queue<int> q;q.push(s);d[s]=0;		while (!q.empty()) {			int x=q.front();q.pop();			for (int i=head[x];i;i=e[i].next)				if (e[i].w && d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to);		}		return d[t]>0;	}	int dfs(int x,int f) {		if (x==t || f==0) return f;		int w,used=0;		for (int i=head[x];i;i=e[i].next) if (e[i].w && d[e[i].to]==d[x]+1) {				w=dfs(e[i].to,min(e[i].w,f-used));				used+=w;e[i].w-=w;e[i^1].w+=w;				if (used==f) return used;			}		if (!used) d[x]=-1;		return used;	}	int main(int x,int y) {		s=x,t=y;int flow=0;		while (bfs(x,y)) flow+=dfs(x,inf);		return flow;	}}int main() {	scanf("%d%d%d",&n,&m,&T);	for (int i=1;i<=m;i++) scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].w);	link(0,1,T);et=1000000;	for (int i=0;1;i++) {		for (int j=1;j<=n;j++) link(i*n+j,(i+1)*n+j,inf);		for (int j=1;j<=m;j++) link(i*n+t[j].u,(i+1)*n+t[j].v,t[j].w);		link((i+1)*n,et,inf);		ans+=Dinic::main(0,et);		if (ans==T) {printf("%d",i);break;}	}	return 0;}