#include<algorithm>
using namespace std;
#include<vector>
#include<queue>
#include<bitset>

#define DIM 1005
#define INF 1<<29
#define pb push_back

vector <int> lst[DIM];
queue <int> q;
bitset <DIM> viz;
int n,m,c[DIM][DIM],f[DIM][DIM],t[DIM],sol;

char buff[DIM];
int poz;
inline void pars (int &nr)
{
    nr=0;
    while(buff[poz]<'0' || '9'<buff[poz])
        if(++poz==DIM)
            fread (buff,1,DIM,stdin),poz=0;
    while(buff[poz]>='0' && '9'>=buff[poz])
    {
        nr=nr*10+buff[poz]-'0';
        if(++poz==DIM)
            fread (buff,1,DIM,stdin),poz=0;
    }
}
void read ()
{
    int i,x,y,z;
    pars(n);
    pars(m);
    for(i=1;i<=m;++i)
    {
        pars(x);
        pars(y);
        pars(z);
        c[x][y]+=z;
        lst[x].pb (y);
        lst[y].pb (x);
    }
}
inline void bf ()
{
    int i,nr;
    for(i=1;i<=n;++i)
        viz[i]=0;
    viz[1]=1;
    q.push (1);
    while(!q.empty ())
    {
        nr=q.front ();
        for(i=0;i<(int)lst[nr].size ();++i)
            if(c[nr][lst[nr][i]]!=f[nr][lst[nr][i]] && !viz[lst[nr][i]])
            {
                t[lst[nr][i]]=nr;
                viz[lst[nr][i]]=1;
                if(lst[nr][i]!=n)
                    q.push (lst[nr][i]);
            }
        q.pop ();
    }
}
inline void solve ()
{
    int minim,i,j;
   bf ();
        for(j=0;j<(int)lst[n].size ();++j)
            if(c[lst[n][j]][n]!=f[lst[n][j]][n] && viz[lst[n][j]])
            {
                t[n]=lst[n][j];
                minim=INF;
                for(i=n;i!=1;i=t[i])
                    minim=min(minim,c[t[i]][i]-f[t[i]][i]);
                if(minim)
                    for(i=n;i!=1;i=t[i])
                    {
                        f[t[i]][i]+=minim;
                        f[i][t[i]]-=minim;
                    }
                sol+=minim;
            }
}
int main ()
{
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    double start=clock ();
    read ();
    while((clock()-start)<=350)
        solve ();
    printf("%d",sol);
    return 0;
}