#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define uv ve[i][j]

using namespace std;

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

int n;
vector<int> ve[1001];
int a[1001][1001];
int pr[1001],fi[1001];
bool ok[1001],ok2[1001];

bool bfs(){
    memset(ok,0,sizeof(ok));
    queue<int> q;
    fi[0]=0;

    ok[1]=1;
    q.push(1);

    while(!q.empty()){
        int i=q.front();
        q.pop();

        for(unsigned j=0;j<ve[i].size();j++){
            if(uv!=n&&!ok[uv]&&a[i][uv]>0){
                ok[uv]=1;
                q.push(uv);
                pr[uv]=i;
            }
            if(uv==n&&a[i][uv]>0)
                fi[++fi[0]]=i;
        }
    }

    return fi[0];
}

void bfs2(){
    ok2[n]=1;
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(unsigned j=0;j<ve[i].size();j++){
            if(!ok2[uv]&&a[i][uv]>0){
                q.push(uv);
                ok2[uv]=1;
            }
        }
    }
    return;
}

int main()
{
    int m;

    f>>n>>m;

    int sl[10001][2]={};

    for(int i=1;i<=m;i++){
        int x,y,cs;
        f>>x>>y>>cs;
        sl[i][0]=x;
        sl[i][1]=y;
        a[x][y]=a[y][x]=cs;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }int s=0;

    while(bfs()){
        for(int t=1;t<=fi[0];t++){
            int i=fi[t],j=n,mn=20000;
            while(i){
                if(a[i][j]<mn) mn=a[i][j];
                j=i;
                i=pr[i];
            }
            i=fi[t],j=n;
            while(i){
                a[i][j]-=mn;
                a[j][i]+=mn;
                j=i;
                i=pr[i];
            }
            s+=mn;
        }
    }

    g<<s;
    return 0;

    bfs2();

    int nr=0;
    for(int i=1;i<=m;i++)
        if( (ok[sl[i][0]]&&ok2[sl[i][1]]) || (ok[sl[i][1]]&&ok2[sl[i][0]]) )
            nr++;
    g<<nr<<'\n';

    for(int i=1;i<=m;i++)
        if((ok[sl[i][0]]&&ok2[sl[i][1]])||(ok[sl[i][1]]&&ok2[sl[i][0]]))
            g<<i<<'\n';

    return 0;
}