#include <fstream>
#include <string.h>
#include <vector>

#define max_n 1001

using namespace std;

int n,m,c[max_n][max_n],f[max_n][max_n];
vector <int> g[max_n];
vector <int>::iterator it;
int t[max_n],fx,r,x,y,z,i,j;

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

int BF() {
    int st,dr,i,q[max_n],nod;
    memset(t,0,sizeof(t));
    st=dr=1;
    q[1]=1;
    while (st<=dr) {
        nod=q[st];
        for (i=1; i<=n; i++)
        //if (a[nod][i]!=0)
            if (i!=nod && t[i]==0 && c[nod][i]>f[nod][i]) {
                dr++;
                q[dr]=i;
                t[i]=nod;
                if (i==n) return 1;
            }
        st++;
    }
    return 0;
}


int main () {
    in >> n >> m;
    memset(c,0,sizeof(c));
    for (i=1; i<=m; i++) {
        in >> x >> y >> z;
        c[x][y]=z;
        g[x].push_back(y);
    }

    fx=0;
    memset(f,0,sizeof(0));
    while (BF()) {
        for (i=1; i<=n; i++) {
            if (t[i]==0 || c[i][n]<=f[i][n])
              continue;
            r=c[i][n]-f[i][n];
            j=i;
            while (j!=1) {
                 r=min(r,c[t[j]][j]-f[t[j]][j]);
                 j=t[j];
            }
            if (r==0) continue;
            f[i][n]+=r;
            f[n][i]-=r;
            j=i;
            while (j!=1) {
                f[t[j]][j]+=r;
                f[j][t[j]]-=r;
                j=t[j];
            }
        fx+=r;
        }
    }
    out << fx << '\n';
    return 0;
}