//var III Edmonds-Karp optimizat 100p
//drumul de ameliorare facut cu BFS
//maresc fluxul pentru pred. lui n
#include <fstream>
using namespace std;
#define MAX 1003
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int A[MAX][MAX];
int infinit=100000000;
int viz[MAX],C[5*MAX];
int n,m;
int T[MAX];

void BFS(int nod)
{
    int p,i,u;
    for(i=1; i<=n; i++)viz[i]=0;
    p=u=1;
    C[1]=1;
    while(p<=u)
    {
        nod=C[p];
        p++;
        for(i=1; i<=n; i++)
            if(A[nod][i]>0 and viz[i]==0)
            {
                C[++u]=i;
                viz[i]=1;
                T[i]=nod;
            }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int xx,yy,cc;
        f>>xx>>yy>>cc;
        A[xx][yy]=cc;
    }
    int flux_final=0;
    while (true)
    {
        BFS(1);
        if (viz[n]==0)break;
        for(int j=1; j<=n; j++) //maresc fluxul la toti pred. lui n
            if(A[j][n]>0) //j pred. a lui n
            {
                //calculez fmax pe drulul de ameliorare (1..j)
                int fmax=A[j][n];
                int i=j;
                while (i!=1)
                {
                    fmax=min(fmax,A[T[i]][i]);
                    i=T[i];
                }
                //scad cu fmax drumul de ameliorare (1..j)
                A[j][n]-=fmax;
                A[n][j]+=fmax;
                i=j;
                while (i!=1)
                {
                    A[T[i]][i]-=fmax;
                    A[i][T[i]]+=fmax;
                    i=T[i];
                }
                flux_final+=fmax;
            }
    }
    g<<flux_final<<'\n';
}
////var II Edmonds-Karp 70p timpul!!
////drumul de ameliorare facut cu BFS
//#include <fstream>
//using namespace std;
// #define MAX 1003
//ifstream f("maxflow.in");
//ofstream g("maxflow.out");
//int A[MAX][MAX];
//int infinit=100000000;
//int viz[MAX],C[5*MAX];
//int n,m;
//int T[MAX];
//
//void BFS(int nod){
//   int p,i,u;
//   for(i=1;i<=n;i++)viz[i]=0;
//   p=u=1;
//   C[1]=1;
//   while(p<=u){
//     nod=C[p];p++;
//     for(i=1;i<=n;i++)
//       if(A[nod][i]>0 and viz[i]==0)
//               {C[++u]=i;
//                viz[i]=1;
//                T[i]=nod;
//                }
//   }
//}
//int main(){
//  f>>n>>m;
//  for(int i=1;i<=m;++i){
//     int xx,yy,cc;
//     f>>xx>>yy>>cc;
//     A[xx][yy]=cc;
//  }
//  int flux_final=0;
//  while (true){
//    BFS(1);
//    if (viz[n]==0)break;
//    int fmax=infinit;
//    int i=n;
//    while (i!=1){
//        fmax=min(fmax,A[T[i]][i]);
//        i=T[i];
//    }
//    i=n;
//    while (i!=1){
//       A[T[i]][i]-=fmax;
//       A[i][T[i]]+=fmax;
//       i=T[i];
//     }
//    flux_final+=fmax;
//  }
//  g<<flux_final<<'\n';
//}

////var I Ford Fulkerson  60p timpul!!
//drumul de ameliorare facut cu DFS
//#include <fstream>
//using namespace std;
// #define MAX 1003
//ifstream f("maxflow.in");
//ofstream g("maxflow.out");
//int A[MAX][MAX];
//int infinit=100000000;
//bool viz[MAX];
//int n,m;
//int T[MAX];
//
//void dfs(int nod){
//   viz[nod]=true;
//   for(int i=1;i<=n;++i){
//      if (viz[i]==false){
//        if (A[nod][i]>0){
//           T[i]=nod;
//           dfs(i);
//           }
//      }
//   }
//}
//int main(){
//  f>>n>>m;
//  for(int i=1;i<=m;++i){
//     int xx,yy,cc;
//     f>>xx>>yy>>cc;
//     A[xx][yy]=cc;
//  }
//  int flux_final=0;
//  while (true){
//    for(int i=1;i<=n;++i){
//       viz[i]=false;
//    }
//    dfs(1);
//    if (viz[n]==false)break;
//    int fmax=infinit;
//    int i=n;
//    while (i!=1){
//        fmax=min(fmax,A[T[i]][i]);
//        i=T[i];
//    }
//    i=n;
//    while (i!=1){
//       A[T[i]][i]-=fmax;
//       A[i][T[i]]+=fmax;
//       i=T[i];
//     }
//    flux_final+=fmax;
//  }
//  g<<flux_final<<'\n';
//}