#include<fstream>
#include<vector>
#include<queue>
#define N 1001
using namespace std;

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

int n,m,co[N][N],flux[N][N],p[N];
vector<pair<int,int> > g[N];
bool viz[N];

bool bf() {
    queue<int> q;
    vector<pair<int,int> >::iterator it;
    int i;

    for(i=1;i<=n;++i) {

        viz[i]=false;
        p[i]=0;
    }

    q.push(1);

    while(!q.empty()) {

        for(it=g[q.front()].begin();it!=g[q.front()].end();++it) if(!viz[it->first] && co[q.front()][it->first] - flux[q.front()][it->first]>0) {

            q.push(it->first);
            p[it->first]=q.front();
            viz[it->first]=true;

        }

        q.pop();
    }

    if(!p[n])
        return 0;
    return 1;

}

void dinic() {
    int i,j,smin;

    while(bf())
        for(j=1;j!=n;++j) if(co[j][n] - flux[j][n]>0) {

            smin=1<<20;

            if(co[j][n] - flux[j][n]<smin)
                smin=co[j][n] - flux[j][n];

            for(i=j;i!=1;i=p[i])
                if(co[p[i]][i] - flux[p[i]][i]<smin)
                    smin=co[p[i]][i] - flux[p[i]][i];

            if(smin==1<<20)
                continue;

            flux[j][n]+=smin;
            flux[n][j]-=smin;

            for(i=j;i!=1;i=p[i]) {

                flux[p[i]][i]+=smin;
                flux[i][p[i]]-=smin;

            }

        }

}

int main() {
    int i,a,b,c;

    in >> n >> m;

    for(i=1;i<=m;++i) {

        in >> a >> b >> c;

        g[a].push_back(pair<int,int>(b,i));
        g[b].push_back(pair<int,int>(a,i));
        co[a][b]=c;
        co[b][a]=c;

    }

    dinic();

    return 0;
}