#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

queue <int> q;

int t[1003],n,Min[1003],cst[1003][1003];
bool viz[1003];
int a[1003][1003],m,x,y,c;

vector <int> G[1003];

void dfs()
{
    int poz=1;
    q.push(poz);
    while(!q.empty()&&t[n]==0)
    {
        poz=q.front();
        q.pop();
        for(int i=0;i<G[poz].size();i++)
        if(viz[G[poz][i]]==0&&a[poz][G[poz][i]]<cst[poz][G[poz][i]])
        {
            viz[G[poz][i]]=1;
            q.push(G[poz][i]);
            Min[G[poz][i]]=min(Min[poz],cst[poz][G[poz][i]]-a[poz][G[poz][i]]);
            t[G[poz][i]]=poz;
        }
    }
    while(!q.empty())
        q.pop();
}


int main()
{
    fin>>n>>m;
    for(int i=1;i <= m; i++)
    {
        fin>>x>>y>>c;
        cst[x][y]=c;
        cst[y][x]=c;
        G[x].push_back(y);
    }
    Min[1]=1000000000;
    dfs();
    while(t[n]!=0)
    {
        x=t[n];
        y=n;
        while(x!=0)
        {
            a[y][x]+=Min[n];
            a[x][y]+=Min[n];
            y=x;
            x=t[x];
        }
        t[n]=0;
        Min[1]=1000000000;
        for(int i=1;i<=n;i++)
            viz[i]=0;
        dfs();
    }
    {
        int ttl=0;
        for(int i=1;i<=n;i++)
            ttl+=a[i][n];
        fout<<ttl;
    }
    return 0;
}