#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define maxn 1010
#define flow(a, b) c[a][b] - f[a][b]
vector<int> g[maxn];
int c[maxn][maxn], f[maxn][maxn];
int bt[maxn], tt[maxn];
queue<int> q;
int n, m;
bool bfs()
{
    q.push(1);
    bt[1] = 1;
    tt[1] = 0;
    int x;
    while(!q.empty())
    {
        x = q.front();
        bt[x] = 1;
        q.pop();
        for (int son: g[x])
            if (!bt[son] && flow(x, son))
                {if(son!=n)
                    q.push(son);
                bt[son] = 1;
                tt[son] = x;
                }
    }
    return bt[n] == 1;
}
int main()
{
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    fin>>n>>m;
    int a, b, cc;
    for (int i = 0; i < m; i++)
    {
        fin>>a>>b>>cc;
        g[a].push_back(b);
        g[b].push_back(a);
        c[a][b] = cc;
    }
    int mlc, j;
    while (bfs())
    {
        memset(bt,0, sizeof(bt));
        for (int i = 1; i < n; i++)
            if (c[i][n] && flow(i, n))
            {
                mlc = flow(i, n);
                j = i;
                while(tt[j])
                {
                    if (mlc > flow(tt[j],j)) mlc = flow(tt[j],j);
                    j = tt[j];
                }
                j = i;
                f[i][n] +=mlc;
                while (tt[j])
                {
                    f[tt[j]][j] +=mlc;
                    //f[j][tt[j]] -=mlc;
                    j = tt[j];
                }
            }
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
        ans +=f[1][i];
    fout<<ans<<'\n';
}