#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

vector<int> vecini[1005];
int capacitate[1005][1005];
int flux[1005][1005];
int viz[1005];
int special[1005];
int tata[1005];
int sol;

int n, m;

void citire(){
    scanf("%d %d", &n, &m);
    int x, y, z;

    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &x, &y, &z);

        vecini[x].push_back(y);
        vecini[y].push_back(x);
        capacitate[x][y] += z;
        flux[x][y] = 0;

        if(y == n){
            special[x] = 1;
        }
    }
}

bool addFlux(int x){
    int xxx = x;

    int xx = x;
    x = tata[x];

    int minim = 99999999;

    minim = min(minim, capacitate[xx][n] - flux[xx][n]);

    while(x != xx){
        minim = min(minim, capacitate[x][xx] - flux[x][xx]);
        xx = x;
        x = tata[x];
    }

    if(minim == 0){
        return 0;
    }

    sol += minim;

    x = xxx;
    xx = x;
    x = tata[x];

    flux[xx][n] += minim;

    while(x != xx){
        flux[x][xx] += minim;
        flux[xx][x] -= minim;
        xx = x;
        x = tata[x];
    }

    return 1;
}

bool bfs(){
    bool ok = false;

    queue<int> Q;

    for(int i = 1; i <= n; i++){
        viz[i] = 0;
    }
    Q.push(1);
    viz[1] = true;
    tata[1] = 1;

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

//        if(special[x] == true){
//            continue;
//        }

        int l = vecini[x].size();

        for(int i = 0; i < l; i++){
            int xx = vecini[x][i];

            if(xx != n && viz[xx] == false && flux[x][xx] != capacitate[x][xx]){
                viz[xx] = true;
                tata[xx] = x;
                Q.push(xx);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        if(viz[i] == 1 && special[i] == 1){
            bool okx = addFlux(i);
            if(okx == 1){
                ok = 1;
            }
        }
    }

    return ok;
}

void afisare(){
    printf("%d", sol);
}

int main()
{
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);

    citire();
    while(bfs());
    afisare();

    return 0;
}