#include <fstream>
#define min(x,y) ((x<y)?(x):(y))
#define abs(x) ((x)>0?x:-x)
using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");
const int N=1001;
int n,m,s,d,viz[N],q[N];
int c[N][N]; //capacitatea fiecarui arc
int f[N][N]; //fluxul fiecarui arc

void citire(){
    int i,x,y,co;
    in>>n>>m;
    s=1;
    d=n;
    for(i=0;i<m;i++){
        in>>x>>y>>co;
        c[x][y]=co;
    }
}
int bfs(){
    //returneaza 1 daca iesirea retelei nu a fost marcata
    int p,u,i,x;
    q[0]=s;
    p=u=0;
    viz[s]=1;
    while(p<=u && !viz[d]){
        x=q[p++];
        for(i=1;i<=n;i++)
            if(!viz[i])
                if(f[x][i]<c[x][i]){
                    viz[i]=x;
                    q[++u]=i;
                }
                else
                    if(f[i][x]>0){
                        viz[i]=-x;
                        q[++u]=i;
                    }
    }
    return !viz[d];
}
void ek(){
    int i,a,b,lg,v;
    int l[N];
    do{
        //marcam varfurile intr-o parcurgere in latime
        for(i=1;i<=n;i++)
            viz[i]=0;
        if(bfs())
            return;
        //determinam lantul de ameliorare in vectorul L
        l[0]=d;
        lg=0;
        a=b=110001;
        while(l[lg]!=s){
            ++lg;
            l[lg]=abs(viz[l[lg-1]]);
            if(viz[l[lg-1]]>0)
                a=min(a,c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]);
                else
                if(viz[l[lg-1]]<0)
                    b=min(b,f[l[lg-1]][l[lg]]);
        }
        v=min(a,b);
        //marim fluxul de-a lungul lantului
        for(i=lg;i>0;i--)
            if(viz[l[i-1]]>0)
                f[l[i]][l[i-1]]+=v;
            else
                f[l[i-1]][l[i]]-=v;
    }while(1);
}
void afisare(){
    int i,j,vf=0;
    for(i=1;i<=n;i++)
        vf+=f[i][d];
    out<<vf;
}
int main(){
    citire();
    ek();
    afisare();
    return 0;
}