#include <bits/stdc++.h>

using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int C[1001][1001];
int F[1001][1001];
int viz[1001];
int l[1001];
queue <int> q;
int n;
bool BFS()
{
    fill(viz+1,viz+n+1,0);
    q.push(1);
    int i,x;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(i=1;i<=n;i++)
        if(!viz[i])
        {
            if(C[x][i]>F[x][i])
            {
                viz[i]=x;
                q.push(i);
            }
            else if(F[i][x]>0)
            {
                viz[i]=-x;
                q.push(i);
            }
        }
    }
    return viz[n];
}
void Edmonds_Karp()
{
    int i,m1,m2,k,val;
    while(BFS())
    {
       m1=m2=2e9+1;
       k=0;
       l[0]=n;
       while(l[k]!=1)
       {
           k++;
           l[k]=viz[l[k-1]];
           if(l[k]>0)
           {
               if(C[l[k]][l[k-1]]-F[l[k]][l[k-1]]<m1)
               m1=C[l[k]][l[k-1]]-F[l[k]][l[k-1]];
           }
           else
           {
               l[k]=-l[k];
               if(F[l[k-1]][l[k]]<m2)
               m2=F[l[k-1]][l[k]];
           }
       }
       val=min(m1,m2);
       for(i=k;i>0;i--)
        if(viz[l[i-1]]>0)
        F[l[i]][l[i-1]]+=val;
        else
        F[l[i-1]][l[i]]-=val;
    }
}
int main()
{
    int m,k,i,j,c;
    f>>n>>m;
    for(k=1;k<=m;k++)
    {
        f>>i>>j>>c;
        C[i][j]=c;
    }
    Edmonds_Karp();
    int sum=0;
    for(i=1;i<=n;i++)
        sum+=F[i][n];
    g<<sum;

    return 0;
}