#include<bits/stdc++.h>

using namespace std;

int const NMax = 1005, CMax = 1000000, oo = 1000000000;
int C[NMax][NMax], D[NMax], use[NMax], pred[NMax];
vector <int> G[NMax], GS[NMax];
queue <int> Q;
int t, n, m, k, l, nr, fm, maxf;

void Read()
{
    int i, x, y, c, j;
    scanf("%d %d", &n, &m);

    for(i = 0; i < m; i++){
        scanf("%d %d %d", &x, &y, &c);
        C[x][y] = max(C[x][y], c);
    }

    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(C[i][j] and i != j){
                G[i].push_back(j);
                G[j].push_back(i);
            }
}

bool lvlGraph()
{
    int i, node;
    for(i = 0; i <= n; i++){
        GS[i].clear();
        D[i] = oo;
    }
    D[1] = 0;
    Q.push(1);
    while(Q.size()){
        node = Q.front();
        Q.pop();
        for(auto it : G[node])
            if(C[node][it] and D[it] == oo){
                D[it] = D[node] + 1;
                Q.push(it);
            }
    }
    if(D[n] == oo)
        return 0;
    Q.push(n);
    while(Q.size()){
        node = Q.front();
        Q.pop();
        for(auto it : G[node])
            if(D[it] == D[node] - 1){
                GS[it].push_back(node);
                Q.push(it);
            }
    }
    return 1;
}

void DFS(int node)
{
    use[node] = 1;
    for(vector<int>::iterator it = GS[node].begin(); it != GS[node].end();)
        if(!C[node][*it] and !use[*it])
            GS[node].erase(it);
        else
            it++;

    for(auto it : G[node])
        if(C[node][it] and !use[it]){
            pred[it] = node;
            DFS(it);
        }
}

void augment(int node, int minEdge)
{
    if(node == 1){
        fm = minEdge;
        maxf += fm;
        return;
    }
    else{
        augment(pred[node], min(minEdge, C[pred[node]][node]) );
        C[pred[node]][node] -= fm;
        C[node][pred[node]] += fm;
    }
    //Source: Competitive Programming 3 by Steven Halim and Felix Halim, page 165
}

void Solve()
{
    int i;
    while(lvlGraph()){
        do{
            memset(use, 0, sizeof(use));
            memset(pred, 0, sizeof(pred));
            DFS(1);
            if(!use[n])
                break;
            augment(n, oo);
        }
        while(1);
    }
    printf("%d\n", maxf);
}

int main()
{
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    Read();
    Solve();
    return 0;
}