#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define setinf(x) memset(x,0x3f3f3f3f,sizeof(x));
#define set0(x) memset(x,0,sizeof(x));
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define fi first
#define se second
#define DD 100001
#define nl '\n'
using namespace std;
const string file="maxflow";
ifstream f(file+".in");
ofstream g(file+".out");
//#define f cin
//#define g cout
struct dinic {
    int n,s,t;
    struct edge {
        int to,rez,cap;
    };
    vector<vector<edge>>v;
    vi id,lvl;
    dinic(int _n, int _s, int _t) {
        n=_n,s=_s,t=_t;
        v.resize(n+1,{});
        id.resize(n+1);
        lvl.resize(n+1);
    }
    void add(int x, int y, int c) {
        edge a{y,(int)v[y].size(),c};
        edge b{x,(int)v[x].size(),0};
        v[x].push_back(a);
        v[y].push_back(b);
    }
    bool bfs() {
        fill(all(lvl),-1);
        queue<int> q;
        q.push(s);
        lvl[s]=0;
        while (!q.empty()) {
            int x=q.front();
            q.pop();
            for (auto e:v[x]) {
                if (e.cap>0 && lvl[e.to]==-1) {
                    lvl[e.to]=lvl[x]+1;
                    q.push(e.to);
                }
            }
        }
        return lvl[t]!=-1;
    }
    int dfs(int x, int flow) {
        if (x==t) return flow;
        for (int &i=id[x]; i<(int)v[x].size(); i++) {
            edge &e=v[x][i];
            if (e.cap>0 && lvl[e.to]==lvl[x]+1) {
                int bneck=dfs(e.to,min(flow,e.cap));
                if (bneck>0) {
                    e.cap-=bneck;
                    v[e.to][e.rez].cap+=bneck;
                    return bneck;
                }
            }
        }
        return 0;
    }
    int maxflow() {
        int mxfl=0;
        while (bfs()) {
            fill(all(id),0);
            while (int fl=dfs(s,INF)) mxfl+=fl;
        }
        return mxfl;
    }
};
int main(){
    int n,m;
    f>>n>>m;
    dinic v(n,1,n);
    for (int i=1; i<=m; ++i) {
        int x,y,c;
        f>>x>>y>>c;
        v.add(x,y,c);
    }
    g<<v.maxflow();
    system("pause");
    return 0;
}