#include <iostream>
#include <limits.h>
#include <fstream>
using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");
int bfs(int n,int rgraf[][501], int s, int d, int parinte[])
{
    int viz[501],i,p,u;
    for (i=1; i<=n; i++)
        viz[i]=0;
    int q[101];
    p=u=1;
    q[p]=s;
    viz[s] = 1;
    parinte[s] = -1;
    while (p<=u)
    {
        int x = q[p];
        for (int i = 1; i <= n; i++)
        {
            if (viz[i] == 0 && rgraf[x][i] > 0)
            {
                if (i == d)
                {
                    parinte[i] = x;
                    return 1;
                }
                u++;
                q[u]=i;
                parinte[i] = x;
                viz[i] = 1;
            }
        }
        p++;
    }
    return 0;
}

/// returneaza fluxul maxin de la sursa la destinatie
int FordFulkerson(int n,int graf[][501], int s, int d)
{
    int i, j;

    // Create a residual graph and fill the residual graph
    // with given capacities in the original graph as
    // residual capacities in residual graph
    int rgraf[501][501]; // Residual graph where rGraph[i][j]
    // indicates residual capacity of edge
    // from i to j (if there is an edge. If
    // rGraph[i][j] is 0, then there is not)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            rgraf[i][j] = graf[i][j];

    int parinte[501];
    int flux_max = 0;

    while (bfs(n,rgraf, s, d, parinte)==1)
    {

        int path_flow = INT_MAX;
        for (j = d; j != s; j = parinte[j])
        {
            i = parinte[j];
            if (path_flow>rgraf[i][j])
                path_flow=rgraf[i][j];
            /// path_flow = min(path_flow, rgraf[i][j]);
        }
        for (j = d; j != s; j = parinte[j])
        {
            i = parinte[j];
            rgraf[i][j] = rgraf[i][j] - path_flow;
            rgraf[j][i] =  rgraf[j][i] + path_flow;
        }
        flux_max =flux_max+ path_flow;
 /*       cout<<flux_max<<endl;
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
                cout<<rgraf[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
   */
    }
    return flux_max;
}

int main()
{
    /* alt exemplu
       int graf[][]
         = { { 0, 16, 13, 0, 0, 0 }, { 0, 0, 10, 12, 0, 0 },
             { 0, 4, 0, 0, 14, 0 },  { 0, 0, 9, 0, 0, 20 },
             { 0, 0, 0, 7, 0, 4 },   { 0, 0, 0, 0, 0, 0 } };
    */

    int n,m,graf[501][501],x,y,c,i,s,d;
    f>>n>>m;
    for (i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        graf[x][y]=c;
    }
    //f>>s>>d;
    s=1;d=n;
    //cout << "Fluxul maxim= "
        g << FordFulkerson(n,graf, s, d);
    return 0;
}