#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define FIN "maxflow.in"
#define FOUT "maxflow.out"
#define MAX_N 1005
#define INF 2000000000

vector <int> G[MAX_N], L;

int F[MAX_N][MAX_N];
int C[MAX_N][MAX_N];
int N, M, Res, S, D, len;
int v[MAX_N], deg[MAX_N], c[MAX_N];

    void readdata ()
    {
         int i, a, b, c;
         scanf ("%d %d\n", &N, &M);
         for (i = 1; i <= M; ++i)
         {
             scanf ("%d %d %d", &a, &b, &c);
             G[a].push_back(b);
             G[b].push_back(a);
             C[a][b] = c;
             
             if (b == N) L.push_back(a);
         }
         for (i = 1; i <= N; ++i) deg[i] = G[i].size ();
         len = L.size ();
         S = 1, D = N;
    }
    
    inline int MIN (int a, int b) {
           if (a < b) return a; else return b;
    }

    int BFS ()
    {
        int li, lf, nod, i, it;
        memset (v, 0, sizeof (v));
        li = lf = 0;
        v[S] = -1, c[++lf] = S;
        while (li < lf)
        {
              nod = c[++li];
              for (i = 0; i < deg[nod]; ++i)
                  if (!v[G[nod][i]] && C[nod][G[nod][i]] > F[nod][G[nod][i]])
                  {
                          v[G[nod][i]] = nod;
                          c[++lf] = G[nod][i];
                  }
        }
        
        if (v[D])
        {
                 int ret = 0;
                 for (it = 0; it < len; ++it)
                 {
                     int inc = C[L[it]][N] - F[L[it]][N];
                     if (!v[L[it]]) continue;
                     for (i = L[it]; i != S; i = v[i])
                         inc = MIN (inc, C[v[i]][i] - F[v[i]][i]);
                     F[L[it]][N] += inc;
                     for (i = L[it]; i != S; i = v[i])
                         F[v[i]][i] += inc, F[i][v[i]] -= inc;
                     ret += inc;
                 }
                 return ret;
        }
        return 0;
    }
    
    void solve ()
    {
         int c, i;
         while (c = BFS ())
               Res += c;
         printf ("%d\n", Res);
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        readdata ();
        solve ();
        
        return 0;
    }