/**************************************************************

     Problem: 1570

     User: rausen

     Language: C++

     Result: Accepted

     Time:24 ms

     Memory:15936 kb

 ****************************************************************/

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N = ;

 const int M = ;

 const int inf = 1e8;

 inline int read() {

     int x = ;

     char ch = getchar();

     while (ch < '' || '' < ch)

         ch = getchar();

     while ('' <= ch && ch <= '') {

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }

 struct Edge {

     int x, y, z;

     inline void read_in() {

         x = read(), y = read(), z = read();

     }

 } E[M];

 struct edge {

     int next, to, f;

     edge() {}

     edge(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {}

 } e[M << ];

 int n, m, t;

 int S, T, ans;

 int first[M], tot = ;

 int d[M], q[M];

 inline void Add_Edges(int x, int y, int f) {

     e[++tot] = edge(first[x], y, f), first[x] = tot;

     e[++tot] = edge(first[y], x, ), first[y] = tot;

 }

 #define y e[x].to

 #define p q[l]

 bool bfs() {

   int l, r, x;

   memset(d, -, sizeof(d));

   d[q[] = S] = ;

   for (l = r = ; l != r + ; ++l)

     for (x = first[p]; x; x = e[x].next)

       if (!~d[y] && e[x].f) {

     d[q[++r] = y] = d[p] + ;

     if (y == T) return ;

       }

   return ;

 }

 #undef p

 int dfs(int p, int lim) {

   if (p == T || !lim) return lim;

   int x, tmp, rest = lim;

   for (x = first[p]; x && rest; x = e[x].next)

     if (d[y] == d[p] +  && ((tmp = min(e[x].f, rest)) > )) {

       rest -= (tmp = dfs(y, tmp));

       e[x].f -= tmp, e[x ^ ].f += tmp;

       if (!rest) return lim;

     }

   if (rest) d[p] = -;

   return lim - rest;

 }

 #undef y

 int Dinic() {

   int res = ;

   while (bfs())

     res += dfs(S, inf);

   return res;

 }

 int main() {

     int i, j;

     n = read(), m = read(), t = read();

     for (i = ; i <= m; ++i) E[i].read_in();

     S = , T = ;

     Add_Edges(S, , t);

     for (i = ; i <= n + t; ++i) {

         for (j = ; j <= m; ++j)

             Add_Edges(i * n - n + E[j].x + , i * n + E[j].y + , E[j].z);

         for (j = ; j <= n; ++j)

             Add_Edges(i * n - n + j + , i * n + j + , inf);

         Add_Edges(i * n + n + , T, inf);

         ans += Dinic();

         if (ans == t) {

             printf("%d\n", i);

             return ;

         }

     }

 }