#include <fstream>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;
const int NMAX = 1002;
const int MMAX = 5002;
const int INF = 21e8;

ifstream cin("maxflow.in");
ofstream cout("maxflow.out");

int n;
int cap[NMAX][NMAX]; ///capacitatea init
int adj[NMAX][NMAX];
int viz[NMAX], tata[NMAX];

bool bfs() {
    for(int nod = 1; nod <= n; nod++)
        viz[nod] = tata[nod] = 0;
    viz[1] = 1;
    queue <int> q;
    q.push(1);
    while(!q.empty()) {
        int start = q.front();
        q.pop();
        for(int nod = 1; nod <= n; nod++) {
            if((!viz[nod]) && adj[start][nod] < cap[start][nod]) { ///adica mai avem ce sa pompam
                tata[nod] = start;
                viz[nod] = 1;
                q.push(nod);
            }
        }
    }
    return viz[n];
}
int recons(int nod) {
    tata[n] = nod;
    nod = n; ///ca sa incepem de la ult
    int minn = INF;
    while(nod != 1) {
        int val = cap[tata[nod]][nod] - adj[tata[nod]][nod];
        if(val <= 0)
            return -1;
        minn = min(minn, val);
        nod = tata[nod];
    }
    return minn;
}
void update(int nod, int add) {
    nod = n;
    while(nod != 1) {
        adj[tata[nod]][nod] += add;
        if(nod != n)
            adj[nod][tata[nod]] -= add; ///pe inversa
        nod = tata[nod];
    }
}

int main()
{
    int m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        cap[a][b] += cost;
    }
    int flux = 0;
    while(bfs()) { ///cat timp mai POT sa pompez flux
        /*cout << "uhoh\n";
        for(int i = 1; i <= n; i++)
            cout << tata[i] << " ";
        cout << '\n';*/
        for(int i = 1; i < n; i++){
            if(viz[i] && adj[i][n] < cap[i][n]) { ///se mai poate
                int add = recons(i);
                if(add != -1) {
                    flux += add;
                    update(i, add);
                }
            }
        }
    }
    cout << flux;
    return 0;
}
/*
30 55
1 2 186
1 3 374
1 4 691
1 5 99
1 6 777
1 7 230
1 8 513
1 9 407
1 10 74
1 11 619
3 12 883
6 13 722
9 14 263
9 15 371
8 16 988
2 17 509
7 18 931
6 19 98
6 20 449
6 21 707
19 22 850
18 23 163
21 24 759
23 25 714
18 26 719
20 27 77
9 28 504
17 29 913
20 30 69
21 30 994
22 30 234
23 30 551
24 30 933
25 30 819
26 30 362
27 30 90
28 30 700
29 30 606
10 2 1005
6 19 477
22 21 943
3 2 588
24 5 610
2 24 465
8 12 328
23 4 512
16 11 633
28 16 284
20 24 844
12 13 61
11 5 613
12 19 873
7 13 552
11 13 611
6 3 73
*/