#include <fstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>

using namespace std;

int const nmax = 1000;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

struct Edge
{
    int to;
    int rev; //indicele muchiei inverse in g[to]
    int flow;
    int cap;
};

vector<Edge> g[1 + nmax];
int n, m, src, dest;
int cap[1 + nmax][1 + nmax];


void addedge(int i, int j)
{
    Edge direct  = {j, g[j].size(), 0, cap[i][j]}; //de la i la j
    Edge inverse = {i, g[i].size(), 0, cap[j][i]}; //de la j la i
    g[i].push_back(direct);
    g[j].push_back(inverse);
}


void read()
{
    in >> n >> m;
    src = 1;
    dest = n;
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        in >> x >> y >> z;
        cap[x][y] = z;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if(cap[i][j] != 0 || cap[j][i] != 0)
                addedge(i, j);
        }
    }
}

int dist[1 + nmax];
//acest dist iti creeaza un level graph
//se calculeaza in BFS si pe baza aceste distante, se optimizeaza DFS

bool bfs()   //la fiecare bfs se construieste un level graph
{
    fill(dist + 1, dist + n + 1, -1);
    queue < int > q;
    q.push(src);
    dist[src] = 0;
    while(!q.empty())
    {
        int from = q.front();
        q.pop();
        for(int i = 0; i < g[from].size(); i++)
        {
            Edge &e = g[from][i];
            int to = e.to;
            if(dist[to] < 0 && e.flow < e.cap)
            {
                dist[to] = dist[from] + 1;
                q.push(to);
            }
        }
    }
    return (0 <= dist[dest]);
}

int rem[1 + nmax]; //care ne aminteste noua in dfs ce vecini/muchii am analizat

int dfs(int from, int deltaflow)    //deltaflow tine minte minimul cu care augmentezi
{
    if(from == dest)
        return deltaflow;
    else
    {
        for(int i = rem[from]; i < g[from].size(); i++)
        {
            Edge &e = g[from][i];
            if(dist[e.to] == dist[from] + 1)
            {
                int addflow = dfs(e.to, min(deltaflow, e.cap - e.flow));
                if(0 < addflow)
                {
                    e.flow += addflow;
                    g[e.to][e.rev].flow -= addflow;
                    rem[from] = i;
                    return addflow;
                }
            }
        }
        return 0;
    }
}

int maxflow()
{
    int result = 0;
    while(bfs())   //atata timp cat exista un drum minim intre sursa si destinatie
    {
        //level graph-ul a fost creat in BFS();
        fill(rem + 1, rem + n + 1, 0);
        while(int deltaflow = dfs(src, INT_MAX))   //se fac mai multe path-uri pe care se augmenteaza
        {
            result += deltaflow;
        }
    }
    return result;
}

int main()
{
    read();

    out << maxflow() << '\n';

    in.close();
    out.close();
    return 0;
}