#include <bits/stdc++.h>

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

const int NMAX = 1005, INF = 0x3f3f3f3f;

int N, M, X, Y, Z, T[NMAX];

int C[NMAX][NMAX], F[NMAX][NMAX];

vector < int > G[NMAX];

void Load ()
{
    f.tie(NULL);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> X >> Y >> Z;
        C[X][Y] = Z;
        G[X].push_back(Y);
        G[Y].push_back(X);
    }
}

bool BFS () {
    queue < int > Q;
    for(int i = 1; i <= N; ++i)  T[i] = -1;

    T[1] = 0; Q.push(1);

    while(!Q.empty()){
        int Nod = Q.front();
        Q.pop();

        for(auto i : G[Nod])
            if(T[i] == -1 && C[Nod][i] > F[Nod][i]) {
                T[i] = Nod;
                if(i == N)
                    return 1;
                Q.push(i);
            }
    }
    return 0;
}

int Flux_Max() {
    int ans = 0;

    while(BFS())  {
        for(auto i : G[N])
            if(T[i] != -1) {
                int r = C[i][N] - F[i][N];
                int Nod = i, x = 0;
                while(Nod != 1){
                    x = T[Nod];
                    r = min(r, C[x][Nod] - F[x][Nod]);
                    Nod = x;
                }

                ans += r; F[i][N] += r;  F[N][i] -= r;

                Nod = i;
                while(Nod != 1){
                    x = T[Nod];
                    F[x][Nod] += r;
                    F[Nod][x] -= r;
                    Nod = x;
                }
            }
    }

    return ans;
}

int main()
{
    Load();

    g << Flux_Max() << '\n';

    return 0;
}