#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define maxN 1001
using namespace std;

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

vector <int> graph[maxN];
int cost[maxN][maxN];
int fl[maxN][maxN];
int tata[maxN];
int flux=0;
int st;
int dr;
 queue <int> q;
int bfs()
{
    int ok=0;
    memset(tata,0,sizeof(tata));
    tata[st]=-1;
    q.push(st);

    while(!q.empty())
    {
        int nod=q.front();
         q.pop();
        for(auto &it : graph[nod])
            if(tata[it] == 0 && cost[nod][it] > fl[nod][it])
            {
                if(it != dr)
                {
                    tata[it] = nod;
                    q.push(it);
                }
                else ok = 1;
            }
    }

    return ok;
}

void dinic()
{
    for(int drum = bfs(); drum; drum=bfs())
        for(auto &it : graph[dr])
            if(tata[it] && cost[it][dr] > fl[it][dr])
            {
                tata[dr] = it;
                int min=0x7fffffff;
                for(int nod = dr; nod != st; nod = tata[nod])
                    if( min > cost[tata[nod]][nod] - fl[tata[nod]][nod])
                        min = cost[tata[nod]][nod] - fl[tata[nod]][nod];
                if(min <= 0)
                    continue;
                flux += min;

                for(int nod = dr; nod != st; nod = tata[nod])
                {
                    fl[tata[nod]][nod] += min;
                    fl[nod][tata[nod]] -= min;
                }
            }
}


int main()
{
    int n,m,x,y;
    memset(cost,0,sizeof(cost));
    memset(fl,0,sizeof(fl));

    fin >> n >> m;

    while(m--)
    {

        fin >> x >> y;
        fin >> cost[x][y];
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    st = 1;
    dr = n;
    dinic();

    fout <<  flux;



    return 0;
}