#include <string.h>
#include <limits.h>
#include <stdio.h>
#include <vector>
#include <queue>

#define NMX 1024
#define FOR(a) for(vector<int>::iterator i=v[a].begin();i!=v[a].end();++i)
#define cf(a,b) C[a][b]-F[a][b]
using namespace std;

int n,m;
vector<int> v[NMX];
int F[NMX][NMX];
int C[NMX][NMX];
int h[NMX];
long e[NMX];
bool vis[NMX];
queue<int> q;


int main()
{
  freopen("maxflow.in","r",stdin);
  freopen("maxflow.out","w",stdout);
  
  scanf("%d %d",&n,&m);
  for(int i=0;i<m;i++)
  {
    int j,k,c;
    scanf("%d %d %d",&j,&k,&c);
    v[j].push_back(k);
    C[j][k]+=c;
  }
  FOR(1)
  {
    F[1][*i]=C[1][*i];
    F[*i][1]=-C[1][*i];
    e[*i]=C[1][*i];
    vis[*i]=true;
    q.push(*i);
  }
  while(!q.empty())
  {
    int tp=q.front();
 //   printf("%d\n",tp);
    FOR(tp)
    {
      if(h[tp]<=h[*i]||cf(tp,*i)<=0)continue;
      int tmp = min(e[tp],(long)cf(tp,*i));
      F[tp][*i]+=tmp;
      F[*i][tp]-=tmp;
      e[*i]+=tmp;
      e[tp]-=tmp;
      if(!vis[*i]&&e[*i]>0&&*i!=n&&*i!=1)
      {
        vis[*i]=true;
        q.push((*i));
      }
      if(e[tp]<=0)
        break;
    }
    if(e[tp]>0)
    {
      int minn=INT_MAX;
      FOR(tp)
        if(cf(tp,*i)>0)
          minn=min(minn,h[*i]);
      h[tp]=minn+1;
    }
    else
    {
      q.pop();
      vis[tp]=false;
    }
  }
  printf("%ld\n",e[n]);
}