#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 1099
#define INF 1000000000
using namespace std;
int fin[nmax],fout[nmax];
int res[nmax][nmax];
int s,t,f;
vector <int> p(nmax,0);

void augmentare(int v,int Mmin)
{
if(v==s){f=Mmin;return;}
    else if(p[v]!=-1){
            augmentare(p[v],min(Mmin,res[p[v]][v]));
            res[p[v]][v]-= f; res[v][p[v]]+=f;
    }
}


int main()
{
    int n,m,x,y,c,i;
    ifstream cin("maxflow.in");
    cin>>n;
    //cin>>s>>t;
    s=1;
    t=n;
    cin>>m;

    int ok=1;
    for(i=1;i<=m;i++)
    {   int f;
        cin>>x>>y>>c;
        f=0;
        res[x][y]+=c-f;
       // res[y][x]=c;
        ok= ok && (c>=f);
        fout[x]+=f;
        fin [y]+=f;
    }
    for(i=1;i<=n;i++)
    if(i!=s && i!=t)
    {
        ok= ok && (fout[i]==fin [i]);
        //F intreare == f iesire daca nu e s sau t
    }
    ok = ok && (fout[s]==fin[t]);
    /*
    if(!ok){cout<<"Nu e un flux corect!";return 0;}
    cout<<"Da\n";
    */
    //BFS:
    int mf=0;
    while(1)
    {
        f=0;
        queue<int> q; q.push(s);
        vector<int> dist(n+1,0);
        p.assign(nmax,-1);
        int u,v;
        while(!q.empty())
        {
            u=q.front(); q.pop();

            if(u==t)break;
            for(v=1;v<=n;v++)
                if(res[u][v]>0 && dist[v]==0)
                    {dist[v]=dist[u]+1 , q.push(v), p[v]=u;
                    }
        }
        augmentare(t,INF);

        if(f==0)break;
        mf+=f;
    }
    ofstream cout("maxflow.out");
    cout<<mf;

}