#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1005;
const int inf = 1e9;
int n,m;
int F[NMAX][NMAX], cf[NMAX][NMAX], edg[NMAX][NMAX];
vector < int > v[NMAX];
int e[NMAX], h[NMAX];

void initializare_preflux(int s, int t){
    h[s] = n;
    for(auto it: v[s]){
        cf[it][s] += F[s][it];
        cf[s][it] -= F[s][it];
        e[it] = F[s][it];
    }
}

void pompare(int u, int v){
    //cout << "Pompare de la " << u << " la " << v << " " << min(e[u], cf[u][v]) <<"\n";
    int delta = min(e[u], cf[u][v]);
    if(edg[u][v])
        F[u][v] += delta;
    else
        F[v][u] -= delta;
    cf[u][v] -= delta;
    cf[v][u] += delta;
    e[u] -= delta;
    e[v] += delta;
}

int main(int argc, char**argv){
    f >> n >> m;
    for(int i = 1 ; i <= m ; i++){
        int x, y, z;
        f >> x >> y >> z;
        //x++;
       // y++;
        v[x].push_back(y);
        v[y].push_back(x);
        F[x][y] += z;
        cf[x][y] += z;
        edg[x][y] = 1;
    }

    initializare_preflux(1, n);

    while(true){

        bool flag = false;
        for(int node = 2 ; node < n && !flag ; node++)
            if(e[node] > 0)
                for(auto nxt : v[node])
                    if(cf[node][nxt] > 0 && h[node] == h[nxt] + 1){
                        pompare(node, nxt);
                        flag = true;
                    }

        if(flag) continue;

        for(int node = 2 ; node < n && !flag ; node++){
            if(e[node] <= 0) continue;

            int hmin = inf;
            for(auto nxt: v[node])
                if(cf[node][nxt])
                    hmin = min(hmin, h[nxt]);

            if(hmin >= h[node]){
                //cout << "Inaltare " << node << "\n";
                h[node] = hmin + 1;
                flag = true;
            }
        }

        if(flag) continue;

        break;
    }

    //for(int i = 1 ; i <= n ; i++)
        g << e[n] << " ";

    return 0;
}