#include<iostream>
#include<cstring>
#include<fstream>
#include<vector>
#define NMAX 1001
#include<queue>
#define inf 10000000
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int c[NMAX][NMAX],f[NMAX][NMAX],t[NMAX];
int n,m,s,d,flux;
vector<int>g[NMAX];
void read()
{
    fin>>n>>m;
    s=1;d=n;
    int x,y,ct;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>ct;
        c[x][y]=ct;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    fin.close();
}
int bfs()
{
    queue<int>q;
    memset(t,0,sizeof(t));
    t[s]=-1;
    q.push(s);
    int ok=0;
    for(int nod;!q.empty();q.pop())
    {
        nod=q.front();
        for(vector<int>::iterator it=g[nod].begin();it!=g[nod].end();++it)
              if(t[*it]==0&&c[nod][*it]>f[nod][*it])
        {
            if(*it!=d)
            {t[*it]=nod;
                q.push(*it);
            }
        else ok=1;
        }
    }
    return ok;
}
void dinic()
{
    for(int drum=bfs();drum;drum=bfs())
          for(vector<int>::iterator it=g[d].begin();it!=g[d].end();++it)
               if(t[*it]&&c[*it][d]>f[*it][d])
    {
        t[d]=*it;
        int mn=inf;
        for(int nod=d;nod!=s;nod=t[nod])
             mn=min(mn,c[t[nod]][nod]-f[t[nod]][nod]);
        if(mn<=0)continue;
        flux+=mn;
        for(int nod=d;nod!=s;nod=t[nod])
             f[t[nod]][nod]+=mn,
             f[nod][t[nod]]-=mn;
    }
}
int main()
{
read();
dinic();
fout<<flux<<" ";
fout.close();
return 0;
}