#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
struct edge{
    int a,b,cap, flow;
};
struct Dinic{
    vector<vector<int>> g;
    vector<edge> edges;
    vector<int> level,wh;
    int s,t;
    void build(int n, int _s, int _t){
        g.resize(n+1),level.resize(n+1),wh.resize(n+1);
        s = _s;
        t = _t;
    }
    void add_edge(int a, int b , int cap){
        int m = edges.size();
        edges.push_back({a,b,cap,0});
        edges.push_back({b,a,0,0});
        g[a].push_back(m);
        g[b].push_back(m+1);
    }
    bool bfs(){
        level[s] = 0;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int node = q.front();
            q.pop();
            for(auto i : g[node]){
                edge x = edges[i];
                if(x.cap-x.flow < 1 || level[x.b] != -1){
                    continue;
                }
                level[x.b]=level[node]+1;
                q.push(x.b);
            }
        }
        return level[t]!=-1;
    }
    int dfs(int node, int push){
        if(push == 0 || node==t){
            return push;
        }
        for(int& i = wh[node]; i < (int)g[node].size(); i++){
            edge x = edges[g[node][i]];
            if(x.cap-x.flow < 1 || level[x.b]!=level[node]+1){
                continue;
            }
            int flow = dfs(x.b,min(push,x.cap-x.flow));
            if(flow == 0) continue;
            edges[g[node][i]].flow += flow;
            edges[g[node][i]^1].flow -= flow;
            return flow;
        }
        return 0;
    }
    int flow(){
        int ans = 0;
        while(true){
            fill(level.begin(),level.end(),-1);
            if(!bfs()) break;
            fill(wh.begin(),wh.end(),0);
            while(int add = dfs(s,INT_MAX)){
                ans+=add;
            }
        }
        return ans;
    }
};
int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
    long long n, m;
	fin >> n >> m;
	Dinic G;
	G.build(n, 1, n);
	for (long long i = 1; i <= m; ++i) {
		long long a, b, cost;
		fin >> a >> b >> cost;
		G.add_edge(a, b, cost);
	}
	fout << G.flow();
}