#include <fstream>
#include <vector>

using namespace std;

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

struct el
{
    int y,c;
}q[5005],el;

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

vector <int> G[1003];


void adauga()
{
    q[++k]=el;
    int poz=k;
    while(poz/2>0&&q[poz].c>q[poz/2].c)
    {
        swap(q[poz],q[poz/2]);
        poz/=2;
    }
}

void scoate()
{
    q[1]=q[k];
    k--;
    int poz=1;
    while(1)
    {
        int fiu;
        if(2*poz+1<=k)
        {
            if(q[2*poz].c<q[2*poz+1].c)
                fiu=2*poz+1;
            else
                fiu=2*poz;
        }
        else
        if(2*poz<=k)
            fiu=2*poz;
        else
            return;
        if(q[poz].c>=q[fiu].c)
            break;
        else
        {
            swap(q[poz],q[fiu]);
            poz=fiu;
        }
    }
}




void dfs()
{
    el.y=1;
    el.c=0;
    adauga();
    while(k&&t[n]==0)
    {
        el=q[1];
        scoate();
        int poz=el.y;
        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;
            el.y=G[poz][i];
            Min[G[poz][i]]=min(Min[poz],cst[poz][G[poz][i]]-a[poz][G[poz][i]]);
            el.c=Min[G[poz][i]];
            adauga();
            t[G[poz][i]]=poz;
        }
    }
    k=0;
}


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;
        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;
}