///Max Flow Capacity Scaling
///O(M*M*log(MAX_Capacity))
#include <bits/stdc++.h>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
const int NMAX=1005,INF=0x3F3F3F3F;
int n,m,x,y,c,maxx,scale,new_flow;
struct flux
{
    int flow,capacity;
} graph[NMAX][NMAX];
vector<int>parent;
void dfs(int node,int t,int cur_flow)
{
    for(int i=1; i<=n; i++)
        if(graph[node][i].capacity-graph[node][i].flow>=scale && parent[i]==-1)///if I can still push flow on an edge which fits into the scale and the node is not visited
        {
            cur_flow=min(cur_flow,graph[node][i].capacity-graph[node][i].flow);///second parameter is the number of units of flow I can push through this edge
            parent[i]=node;
            if(i==t)
            {
                new_flow=cur_flow;///we shouldn't reach it after the finding a path
                t=-1;
            }
            dfs(i,t,cur_flow);
        }
}
int maxflow(int s,int t)
{
    int max_flow=0,curr,prev;
    while(scale)
    {
        new_flow=0;
        parent.assign(n+1,-1);
        parent[s]=-2;///so that we cannot reach it afterwards
        dfs(s,t,INF);
        if(new_flow==0)
            scale/=2;
        else
        {
            max_flow+=new_flow;
            curr=t;
            while(curr!=s)
            {
                prev=parent[curr];
                graph[prev][curr].flow+=new_flow;///update on the normal edge
                graph[curr][prev].flow-=new_flow;///update on the reverse edge
                curr=prev;
            }
        }
    }
    return max_flow;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        graph[x][y].capacity=c;///graph[x][y].flow=0 already
        if(c>maxx)
            maxx=c;
    }
    scale=(1<<(int(log2(maxx))));
    g<<maxflow(1,n);///source, terminal
    return 0;
}