#include <bits/stdc++.h>

using namespace std;

ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");

const int NMAX=1005;
int n,m;
int s,t;
int C[NMAX][NMAX]; ///capacitatea fiecarui arc
int F[NMAX][NMAX]; ///fluxul fiecarui arc
vector <pair<int,int>> G[NMAX]; ///1.vecin si 2.sensul (1 direct, -1 invers)

queue<int> Q;
bool viz[NMAX];
int tata[NMAX];
int I; ///capacitatea reziduala a lantului nesaturat

void Citire()
{
    fin>>n>>m;
    s=1; t=n;
    for(int i=1; i<=m; i++)
      {int x,y,c,f;
       fin>>x>>y>>c;
       C[x][y]=c;
       G[x].push_back({y,1});
       G[y].push_back({x,-1});
      }
}



bool ConstruiesteLantNesaturat()
{ /// initializari pentru fiecare BFS
  for(int i=1; i<=n; i++)
    viz[i]=tata[i]=0;
  while(!Q.empty()) Q.pop(); /// golim coada de la apelul anterior
  I=1e9;

  Q.push(s);
  viz[s]=1;
  while(!Q.empty())
   {int u=Q.front();
    Q.pop();
    for(auto node: G[u])
        if(viz[node.first]==0)
         { int v=node.first;
           int sens=node.second;
           if(sens==1)
             {if(C[u][v]-F[u][v]>0)
                {viz[v]=1; Q.push(v); tata[v]=u;
                 I=min(I,C[u][v]-F[u][v]);
                 if(v==t) return 1;
                }
             }
            else {
                if(F[v][u]>0)
                    {viz[v]=1; Q.push(v); tata[v]=-u;
                     I=min(I,F[v][u]);
                     if(v==t) return 1;
                    }
                 }
         }

   }
   return 0;
}


void RevizuiesteLant()
{ int v=t;
  while(v!=s)
    { int u=tata[v]; ///avem arcul (u,v) sau arcul (v,-u)
      if(u>0)
        F[u][v]+=I;
      else F[v][-u]-=I;
      v=abs(u);
    }

}

void EdmondKarp()  ///lanturi nesaturate de lg minima
{
  while(ConstruiesteLantNesaturat())
     RevizuiesteLant();
}

void PunctulB()
{ int flux=0;
  /// flux maxim
  for(int j=1; j<=n; j++)
    flux=flux+F[s][j];
  fout<<flux<<"\n";
  }

int main()
{
    Citire();
    EdmondKarp();
    PunctulB();

    return 0;
}