///Max Flow Push-relabel improved
///O(N*M+N*N*sqrt(M))
#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;
struct flux
{
    int flow,capacity;
} graph[NMAX][NMAX];
vector<int>height,excess;
void push(int node,int next)
{
    int new_flow=min(excess[node],graph[node][next].capacity-graph[node][next].flow);
    graph[node][next].flow+=new_flow;///update on the normal edge
    graph[next][node].flow-=new_flow;///update on the reverse edge
    excess[node]-=new_flow;///update on the current node
    excess[next]+=new_flow;///update on the next node
}
void relabel(int node)
{
    int min_h=INF;
    for(int i=1; i<=n; i++)
        if(graph[node][i].capacity-graph[node][i].flow>0)///meaning we can still push flow through this edge
            min_h=min(min_h,height[i]);
    if(min_h!=INF)
        height[node]=min_h+1;
}
inline vector<int>find_max_height_nodes(int s,int t)
{
    vector<int>max_height;
    for(int node=1; node<=n; node++)
        if(node!=s && node!=t && excess[node]>0)
        {
            if(!max_height.empty() && height[node]>height[max_height[0]])///we found a new maximum
                max_height.clear();
            if(max_height.empty() || height[node]==height[max_height[0]])///we update the vector with the nodes which have a maximum height
                max_height.push_back(node);
        }
    return max_height;
}
int maxflow(int s,int t)
{
    int max_flow=0;
    height.assign(n+1,0);
    height[s]=n+1;
    excess.assign(n+1,0);
    excess[s]=INF;
    for(int i=1; i<=n; i++)
        if(graph[s][i].capacity>0)///if we have an edge between s and i we should push
            push(s,i);
    vector<int>current=find_max_height_nodes(s,t);///returns a vector with the nodes which have excess and a maximum height
    while(!current.empty())///there are nodes with excess and maximum height
    {
        for(int i=0; i<current.size(); i++)
        {
            int node=current[i];
            bool pushed=0;
            for(int next=1; next<=n && excess[node]>0; next++)
            {
                if(graph[node][next].capacity-graph[node][next].flow>0 && height[node]==height[next]+1)
                {
                    push(node,next);
                    pushed=1;
                }
            }
            if(!pushed)
            {
                relabel(node);
                break;
            }
        }
        current=find_max_height_nodes(s,t);///returns a vector with the nodes which have excess and a maximum height
    }
    for(int i=1; i<=n; i++)
        max_flow+=graph[i][t].flow;///if there is no edge,the flow will be 0
    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
    }
    g<<maxflow(1,n);///source, terminal
    return 0;
}