#include <bits/stdc++.h>
#define pb push_back
#define node adjacent[x][i]
using namespace std;

const int N=1005;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

vector<int>adjacent[N];
int inf=(1<<30),source=1;
int flow[N][N],C[N][N],n,m,x,y,c,pre[N];
int q[N],inq[N],b,k,mn,rez;

void bfs(int x)
{
    for(int i=1;i<=n;++i) inq[i]=0;
    k=1; b=0; q[1]=x; inq[x]=1;
    while(b<k)
    {
        ++b;
        x=q[b];
        for(int i=0;i<adjacent[x].size();++i)
        {
            if(!inq[node] && (C[x][node]-flow[x][node]>0))
            {
                pre[node]=x;
                q[++k]=node;
                inq[node]=1;
            }
        }
    }
}

void back_walk(int x)
{
    if(x==source) return;
    mn=min(mn,C[pre[x]][x]-flow[pre[x]][x]);
    back_walk(pre[x]);
    flow[pre[x]][x]+=mn;
}

void optimizare_bolunda_2020_daca_nu_iau_100_mlc(int x)
{
    bool increase_flow=true;
    while(increase_flow)
    {
        increase_flow=0;
        bfs(source);
        for(int i=0;i<adjacent[x].size();++i) if(inq[node] && C[node][x]-flow[node][x]>0)
        {
            mn=C[node][x]-flow[node][x];
            back_walk(node);
            flow[node][x]+=mn;
            rez+=mn;
            if(mn) increase_flow=1;
        }
    }
    g<<rez;
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        C[x][y]=c;
        adjacent[x].pb(y);
        if(y==n) adjacent[y].pb(x);
    }
    optimizare_bolunda_2020_daca_nu_iau_100_mlc(n);
    return 0;
}