#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], nvl[MAX];
bool gasit;

void nivelare(int nod);
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);
    }

    nvl[n] = 1;
    while(nvl[n] != 0)
    {
        for(i = 1; i <= n; i++) nvl[i] = 0;
        nivelare(1);

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

    fout << r;

    return 0;
}

void nivelare(int nod)
{
    queue < int > q;
    q.push(nod), nvl[nod] = 1;
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(auto it:v[nod]) if(a[nod][it].second - a[nod][it].first > 0 && nvl[it] == 0) nvl[it] = nvl[nod] + 1, q.push(it);
    }
}

void dfs(int nod)
{
    int i;

    for(auto it = begin(v[nod]); gasit == 0 && it != end(v[nod]); it++)
        if(a[nod][*it].second - a[nod][*it].first > 0 && nvl[*it] == nvl[nod] + 1)
        {
            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;
            }
        }
}

/// Edmonds-Karp algorithm with Capacity Scaling - Solutie de 70 de puncte (8 teste)
/*
#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 bfs(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;
        bfs(1);
        if(gasit == 1) r += minn;
        else prag /= 2;
    }

    fout << r;

    return 0;
}

void bfs(int nod)
{
    int i;

    queue < int > q;
    q.push(nod), viz[nod] = 1;
    while(q.empty() == 0 && gasit == 0)
    {
        nod = q.front(), q.pop();
        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)
                {
                    gasit = 1, i = *it;
                    while(prec[i] != 0) minn = min(minn, a[prec[i]][i].second - a[prec[i]][i].first), i = prec[i];

                    i = *it;
                    while(prec[i] != 0) a[prec[i]][i].first += minn, a[i][prec[i]].first -= minn, i = prec[i];
                }
                else q.push(*it), viz[*it] = 1;
            }
    }
}
*/

/// Edmonds-Karp algorithm - Solutie de 70 de puncte (7 teste)
/*
#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 bfs(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;
        bfs(1);
        if(gasit == 1) r += minn;
    }

    fout << r;

    return 0;
}

void bfs(int nod)
{
    int i;

    queue < int > q;
    q.push(nod), viz[nod] = 1;
    while(q.empty() == 0 && gasit == 0)
    {
        nod = q.front(), q.pop();
        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)
                {
                    gasit = 1, i = *it;
                    while(prec[i] != 0) minn = min(minn, a[prec[i]][i].second - a[prec[i]][i].first), i = prec[i];

                    i = *it;
                    while(prec[i] != 0) a[prec[i]][i].first += minn, a[i][prec[i]].first -= minn, i = prec[i];
                }
                else q.push(*it), viz[*it] = 1;
            }
    }
}
*/

/// Ford-Fulkerson algorithm with Capacity Scaling - Solutie de 70 de puncte (9 teste)
/*
#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 (7 teste)
/*
#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;
            }
        }
}
*/