#include <bits/stdc++.h>
#define MODL 1000000000000000003
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=5000+9;
int n,m;
int par[N],lev[N];
vector<int> adj[N];
map<pii,ll> edg;
ll dfs(int v,int p,ll mn){
    
    ll tosub=0;
    for(auto u:adj[v])if(u!=p && lev[u]==lev[v]+1 && edg[mp(v,u)]>0){
        ll nmn=min(1ll*mn,edg[mp(v,u)]);
        if(u==n){
            edg[mp(v,u)]-=nmn;
            edg[mp(u,v)]+=nmn;
            return nmn;
        }
        ll sub=dfs(u,v,nmn);
        tosub+=sub;
        if(sub){
            edg[mp(v,u)]-=sub;
            edg[mp(u,v)]+=sub;
        }
    }
    return tosub;

}
int main()
{ 

    ios::sync_with_stdio(false);cin.tie(0);
    int tt=1;//cin>>tt;
    while(tt--){
        edg.clear();
        cin>>n>>m;
        for(int i=0;i<=n;i++){
            adj[i].clear();
        }
        for(int i=0;i<m;i++){
            int x,y,z;
            cin>>x>>y>>z;
            if(x==y)continue;
            adj[x].pb(y);
            adj[y].pb(x);
            edg[mp(x,y)]+=z;
            edg[mp(y,x)]+=z;

        }
        ll ans=0;
        while(1){

            // bfs to find augmenting path
            queue<int> q;
            for(int i=0;i<=n;i++){
                par[i]=lev[i]=-1;
            }
            par[1]=0;lev[1]=1;
            q.push(1);
            bool done=0;
            while(!q.empty()){
                int v=q.front(); q.pop();
                for(auto u:adj[v])if((lev[u]==-1 || lev[u]>lev[v]) && par[u]==-1 && edg[mp(v,u)]>0){
                    if(lev[u]==-1)lev[u]=lev[v]+1;
                    par[u]=v;
                    if(u==n){
                        done=1;
                        break;
                    }
                    q.push(u);
                }
                if(done)break;
            }
            if(done){
                // find blocking flow
                ll add=dfs(1,0,MODL);
                ans+=add;
            } else break;

        }
        cout<<ans<<endl;
    }
    return 0;
}