//Max Flow Push-relabel
//O(N*N*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,used;
queue<int>excess_nodes;
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
    if(new_flow>0 && excess[next]==new_flow)///the second condition is to check if the node is not in the queue already
        excess_nodes.push(next);
}
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;
}
void discharge(int node)
{
    while(excess[node]>0)
    {
        if(used[node]<=n)///in case we did not go through all his neighbours already
        {
            int next=used[node];
            if(graph[node][next].capacity-graph[node][next].flow>0 && height[node]==height[next]+1)///we should not update if the difference is bigger
                push(node,next);
            else
                used[node]++;///we could not update the next node
        }
        else
        {
            relabel(node);
            used[node]=0;
        }
    }
}
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);
    used.assign(n+1,1);///we start the checking from node 1 and we end it with node n
    while(!excess_nodes.empty())
    {
        int node=excess_nodes.front();
        excess_nodes.pop();
        if(node!=s && node!=t)///if the node is not s or t we want to free it from his excess flow
            discharge(node);
    }
    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;
}