#include <bits/stdc++.h>
#define inf 1000000000

using namespace std;

int mat[1000][1000] = {0};
int rez[1000][1000] = {0};
vector<int> v[1000];
vector<int> invn;
int n, m;
int viz[1000];

int main()
{
    int i, j, a, b, c, r;
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        a--; b--;
        v[a].push_back(b);
        mat[a][b] = c;
        if(b == n - 1)
            invn.push_back(a);
    }
    c = 1;
    queue<int> q;
    while(c)
    {
        c = 0;
        for(i = 0; i < n; i++)
            viz[i] = -2;
        viz[0] = -1;
        q.push(0);
        while(!q.empty())
        {
            r = q.front();
            for(i = 0; i < v[r].size(); i++)
            {
                if(viz[v[r][i]] == -2 && mat[r][v[r][i]] != rez[r][v[r][i]])
                {
                    viz[v[r][i]] = r;
                    q.push(v[r][i]);
                }
            }
            q.pop();
        }
        for(i = 0; i < invn.size(); i++)
        {
            if(viz[invn[i]] != -2)
            {
                a = n - 1;
                b = inf;
                while(viz[a] != -1)
                {
                    b = min(b, mat[viz[a]][a] - rez[viz[a]][a]);
                    a = viz[a];
                }
                if(b != 0)
                {
                    c = 1;
                    a = n - 1;
                    while(viz[a] != -1)
                    {
                        rez[viz[a]][a] += b;
                        a = viz[a];
                    }
                }
            }
        }

    }
    c = 0;
    for(i = 0; i < v[0].size(); i++)
    {
        c += rez[0][v[0][i]];
    }
    printf("%d", c);
    return 0;
}