#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];
vector <vector <int>> v;

bitset <NMAX> viz;
vector <int> tata;
bool bfs() {
    viz = 0;
    tata.assign(n + 2, 0);
    viz[1] = 1;
    queue <int> q;
    q.push(1);
    while(!q.empty()) {
        int start = q.front();
        q.pop();
        for(auto nod : v[start]) {
            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;
        adj[nod][tata[nod]] -= add; ///pe inversa
        nod = tata[nod];
    }
}

int main()
{
    int m;
    cin >> n >> m;
    v.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        cap[a][b] += cost;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    /*for(int i = 1; i <= n; i++) {
        cout << "nodul " << i << '\n';
        for(auto nod : v[i])
            cout << nod << " ";
        cout << '\n';
    }*/
    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(auto nod : v[n]) {
            if(viz[nod] && adj[nod][n] < cap[nod][n]) { ///se mai poate
                int add = recons(nod);
                if(add != -1) {
                    flux += add;
                    update(nod, add);
                }
            }
        }
    }
    cout << flux;
    return 0;
}