#include <fstream>
#include <vector>
#include <stack>
using namespace std;


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

const int N_MAX = 1000;
const int M_MAX = 5000;




const int INF = 2147483646;

int capacity[M_MAX];

struct Muchie
{
    int u, v, capacity, flow;

    int getNeighbour(int node)
    {
        return (u+v)-node;
    }

    int getCapacity(int node)
    {
        return node == u ? capacity : 0;
    }

    int getFlow(int node)
    {
        return node == u ? flow:-flow;
    }

    int getResidualCapacity(int node)
    {
        return getCapacity(node) - getFlow(node);
    }

    void addFlow(int node, int value)
    {
        if(node == u) flow += value;
        else flow -= value;
    }
};

vector<Muchie*> vecini[N_MAX];

Muchie* tataM[N_MAX];
int tata[N_MAX];
int minim[N_MAX];

int min(int a, int b)
{
    return (a<b)?a:b;
}

bool vizitat[N_MAX+1];

bool dfs(int N)
{
    minim[N] = INF;
    minim[1] = INF;
    stack<int> frontiera;
    frontiera.push(1);
    for(int i = 2; i <= N; i++) vizitat[i] = false;
    while(!frontiera.empty())
    {
        int nod = frontiera.top();
        frontiera.pop();
        if(nod == N)
            break;
        for(Muchie* m : vecini[nod])
        {
            if((m->getResidualCapacity(nod)!=0) & (!vizitat[m->getNeighbour(nod)]))
            {
                tataM[m->getNeighbour(nod)] = m;
                tata[m->getNeighbour(nod)] = nod;
                minim[m->getNeighbour(nod)] = min(minim[nod], m->getResidualCapacity(nod));
                frontiera.push(m->getNeighbour(nod));
                vizitat[m->getNeighbour(nod)] = true;
            }
        }
    }
    if(minim[N]!=INF)
    {
        Muchie* nod = tataM[N];
        int node = tata[N];
        while(node != 1)
        {
            nod->addFlow(node, minim[N]);
            nod = tataM[node];
            node = tata[node];
        }
        nod->addFlow(1, minim[N]);
        return true;
    }
    else return false;
}

int main()
{
    int N, M;
    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int x, y, z;
        in >> x >> y >> z;
        Muchie* p = new Muchie{x,y,z,0};
        vecini[x].push_back(p);
        vecini[y].push_back(p);
    }
    vizitat[1] = true;
    while(dfs(N));

    int flux = 0;
    for(Muchie* m : vecini[1])
    {
        flux += m->getFlow(1);
    }

    out << flux;
    return 0;
}