#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

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

vector < int > v[MAX];
pair < int, int > a[MAX][MAX];
int n, minn, r, prag, prec[MAX];
bool gasit, viz[MAX];

void dfs(int nod);

int main()
{
    int m, i, x, y, z, maxx = 0;

    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        a[x][y].second = z, maxx = max(maxx, z);
        v[x].pb(y), v[y].pb(x);
    }


    prag = (1<<int(log2(maxx)));
    while(prag != 0)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        minn = INT_MAX, gasit = 0, prec[1] = 0;
        dfs(1);
        if(gasit == 1) r += minn;
        else prag /= 2;
    }

    fout << r;

    return 0;
}

void dfs(int nod)
{
    int i;

    viz[nod] = 1;
    for(auto it = begin(v[nod]); gasit == 0 && it != end(v[nod]); it++)
        if(a[nod][*it].second - a[nod][*it].first >= prag && viz[*it] == 0)
        {
            prec[*it] = nod;

            if(*it != n) dfs(*it);
            else
            {
                gasit = 1, i = *it;
                while(prec[i] != 0) minn = min(minn, a[prec[i]][i].second - a[prec[i]][i].first), i = prec[i];
            }

            if(gasit == 1)
            {
                a[nod][*it].first += minn;
                a[*it][nod].first -= minn;
            }
        }
}

///Ford-Fulkerson algorithm - Solutie de 70 de puncte
/*
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

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

vector < int > v[MAX];
pair < int, int > a[MAX][MAX];
int n, minn, r, prec[MAX];
bool gasit, viz[MAX];

void dfs(int nod);

int main()
{
    int m, i, x, y, z;

    fin >> n >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        a[x][y].second = z;
        v[x].pb(y), v[y].pb(x);
    }

    gasit = 1;
    while(gasit == 1)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        minn = INT_MAX, gasit = 0, prec[1] = 0;
        dfs(1);
        if(gasit == 1) r += minn;
    }

    fout << r;

    return 0;
}

void dfs(int nod)
{
    int i;

    viz[nod] = 1;
    for(auto it = begin(v[nod]); gasit == 0 && it != end(v[nod]); it++)
        if(a[nod][*it].second - a[nod][*it].first > 0 && viz[*it] == 0)
        {
            prec[*it] = nod;

            if(*it != n) dfs(*it);
            else
            {
                gasit = 1, i = *it;
                while(prec[i] != 0) minn = min(minn, a[prec[i]][i].second - a[prec[i]][i].first), i = prec[i];
            }

            if(gasit == 1)
            {
                a[nod][*it].first += minn;
                a[*it][nod].first -= minn;
            }
        }
}
*/