#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream fin("maxflow.in");
ofstream gout("maxflow.out");
 
const int MAXN = 1000;
#define INF 2000000
// https://infoarena.ro/problema/maxflow
//surse de inspiratie:
//codul de seminar pe Google worksheet https://docs.google.com/document/d/1iLRWQZ0QnzlI-q99ynOzdTSyMFZRdEkmXcVM5O_X9NQ/edit?usp=sharing (Laborator 4) scris de un coleg (fara linia noua viz[n]=1 in BFS nu mi-a mers)
//codul dvs cu solutia de 70p https://www.infoarena.ro/job_detail/563495?action=view-source
//codul dvs cu solutia de 100p https://www.infoarena.ro/job_detail/563533?action=view-source
//implementarea de aici  https://www.infoarena.ro/job_detail/2810798?action=view-source, foarte mult modificata
//plus pseudocodul de pe Wikipedia pentru Edmond Karp https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
//in orice caz, miezul acestei probleme e dat de codul discutat la laborator practic

//int c[MAXN][MAXN], f[MAXN][MAXN];
vector<vector<int>> f, c;
//int tata[MAXN], viz[MAXN];
vector<int> tata, viz;
vector<int> g[MAXN];
 
int n, m, act, sink, start, rasp;

void citire()
{       
   /* for (int i = 1; i <= m; i++)
    {
        int x, y, z;

        fin >> x >> y >> z;

        g[x].push_back(y);
        g[y].push_back(x);

        c[x][y] = z;
        f[x][y] = 0;
    }*/

    vector<vector< pair<int, int> >> mc_cost;
    fin >> n >> m;
    int x, y, z;
    mc_cost.resize(n + 1);
    tata.resize(n + 1, 0);
    c.resize(n + 1, vector<int>(n + 1, 0));
    f.resize(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> z;
        mc_cost[x].push_back(make_pair(y, z));
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < mc_cost[i].size(); ++j)
        {
            int nod = get<0>(mc_cost[i][j]);
            int cost = get<1>(mc_cost[i][j]);
            g[i].push_back(nod);
            g[nod].push_back(i);
            c[i][nod] = cost;
        }
}
 
int BFS(int start, int dest)

{     
    queue<int> q;
  //  for (int i = 0; i <= n; ++i)
  //      viz[i] = tata[i] = 0;
    viz.clear();
    tata.clear();
    viz.resize(n + 1, 0);
    tata.resize(n + 1, 0);

    viz[start] = 1;
    q.push(start);
   
    while(!q.empty() && tata[dest]==0) //cand coada nu e goala si cand nu am ajuns inca la destinatie
    {
        int x = q.front();
        q.pop();
        for(auto n :g[x])
        {
            if((c[x][n]-f[x][n]>0) && !viz[n])
            {
                q.push(n);
                tata[n] = x;
                viz[n] = 1;  //linie importanta             
            }
        }       
    } 
return viz[dest];
}
 
void maxflow_si_print()
{
    sink = n;
    start= 1;
    rasp = 0;
    while (BFS(start,sink))
    {
        for (int i = 0; i < g[n].size(); ++i)//si aici partea de imbunatatire expusa de dumneavoastra la laborator
        {
            //calup imbunatatire
            act = g[n][i];
            if ((c[act][n]- f[act][n]==0)|| !viz[act])
                continue;
            tata[n] = act;


            int fmin = INF;

            for (int nod = sink; nod != start; nod = tata[nod])
                fmin = min(fmin, c[tata[nod]][nod] - f[tata[nod]][nod]);

            if (fmin == 0)// tot parte din imbunatatire
                continue;

            for (int nod = sink; nod != start; nod = tata[nod])
            {
                f[tata[nod]][nod] += fmin;
                f[nod][tata[nod]] -= fmin;
            }        
            rasp += fmin;
        }//partea noua de imbunatatiri
    }
    gout << rasp;
}
int main()
{
    citire();
    
    maxflow_si_print();    

    fin.close();
    gout.close();
    return 0;
}