#include <cstdio>
#include <cstring>

using namespace std;

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

typedef struct NOD
{ 
        int nod;
        NOD *next;       
};

int F[MAX_N][MAX_N];
int C[MAX_N][MAX_N];
int V[MAX_N];
int Q[MAX_N];

NOD *A[MAX_N];
int S, D, N, M, mFlow;

    void readdata ()
    {
         int i, x, y, c;
         scanf ("%d %d", &N, &M);
         S = 1, D = N;
         
         for (i = 1; i <= M; ++i)
         {
             scanf ("%d %d %d", &x, &y, &c);
             NOD *p = new (NOD); 
             p->nod = y, p->next = A[x], A[x] = p;
             NOD *q = new (NOD); 
             q->nod = -x, q->next = A[y], A[y] = q;
             C[x][y] = c;
         }
    }
    
    inline int ABS (int a)
    {
           if (a > 0) return a; else return -a;
    }
    
    inline int MIN (int a, int b)
    {
           if (a < b) return a; else return b;
    }

    int BFS ()
    {
        int nod, li, lf;
        li = lf = 0;
        memset (V, 0, sizeof (V));
        Q[++lf] = S, V[S] = 1;
        
        while (li < lf)
        {
              nod = Q[++li];
              for (NOD *q = A[nod]; q != NULL; q = q->next)
                  if (!V[ABS(q->nod)])
                  {
                       if (q->nod > 0)
                          if (F[nod][q->nod] < C[nod][q->nod]) Q[++lf] = q->nod, V[q->nod] = nod;
                       if (q->nod < 0)
                          if (F[-q->nod][nod] > 0) Q[++lf] = -q->nod, V[-q->nod] = -nod;                
                  }
        }
        return V[D];
    }

    void flow ()
    {
         int nod, inc;
         while (BFS())
          for (NOD *q = A[D]; q != NULL; q = q->next)
          if (V[-q->nod])
          {
             inc = C[-q->nod][D] - F[-q->nod][D];
             nod = -q->nod;
             while (nod != S)
             {
                   if (V[nod] > 0) inc = MIN (inc, C[V[nod]][nod] - F[V[nod]][nod]);
                   if (V[nod] < 0) inc = MIN (inc, F[nod][-V[nod]]);
                   nod = ABS (V[nod]);
             }
             
             nod = -q->nod;
             while (nod != S)
             {
                   if (V[nod] > 0) F[V[nod]][nod] += inc;
                   if (V[nod] < 0) F[nod][-V[nod]] -= inc;
                   nod = ABS (V[nod]);
             }
             F[-q->nod][D] += inc; // ultima muchie
          }
         for (NOD *q = A[S]; q != NULL; q = q->next)
             if (q->nod > 0) mFlow += F[S][q->nod];
         printf ("%d\n", mFlow);
    }

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