#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

//surse de inspiratie:
//codul de pe Google worksheet (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];
int tata[MAXN], viz[MAXN];
vector<int> g[MAXN];
 
int n, m, act, source, start, rasp;

void citire()
{
    fin >> n >> m;
    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;

    }
}
 
int BFS(int start, int dest)

{ 
    queue<int> q;
    for (int i = 0; i <= n; ++i)
        viz[i] = tata[i] = 0;
    viz[start] = 1;
    q.push(start);
   
    while(!q.empty())
    {
        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()
{
    source = n;
    start= 1;
    rasp = 0;
    while (BFS(start,source))
    {
        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 (f[act][n] == c[act][n] || !viz[act])
                continue;
            tata[n] = act;


            int fmin = INF;

            for (int nod = source; 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 = source; 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;
}