#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#define mp(a,b) make_pair(a,b)
#define mx 1005
//de lene pentru lemne
using namespace std;

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

int m,n,K;
vector< pair<int,int> > G[mx];// fisrt = nnod||second=flow
bool been[mx];
pair<int,int> ant[mx];// first = from || count on

bool BFS(int source, int sink)//returns if there is a path from start to end
{
    stack<int> S;

    for(int i=1;i<=n;i++)
    {
        been[i]=false;
        ant[i].first=-1;
    }

    for(S.push(source);S.size();)
    {
        int actual=S.top();
        S.pop();
        if(actual==sink)
        {
            return true;
        }

        for(int i=0;i<G[actual].size();i++)
        {
            if(!been[G[actual][i].first] && G[actual][i].second>0)
            {
                //cout<<actual<<' '<<G[actual][i].first<<'\n';
                been[G[actual][i].first]=true;
                ant[G[actual][i].first].first=actual;
                ant[G[actual][i].first].second=i;
                S.push(G[actual][i].first);
            }
        }
    }
return false;
}

int GetMin()
{
    int mn = 110005;
    for(int i=n;i!=1;i=ant[i].first)
    {
        mn=(mn<G[ant[i].first][ant[i].second].second) ? mn:G[ant[i].first][ant[i].second].second;
    }
    return mn;
}

void ReduceWMin(int mn)
{
    for(int i=n;i!=1;i=ant[i].first)
    {
        G[ant[i].first][ant[i].second].second-=mn;
    }
}

int Edmonds()
{
    int MaxFlow=0;
    while(BFS(1,n))
    {
        ReduceWMin(GetMin());
    }
    for(int i=0;i<G[1].size();i++)
    {
        MaxFlow+=G[1][i].second;
    }
    MaxFlow=K-MaxFlow;
}

void Read()
{
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        int from, to, flow;
        f>>from>>to>>flow;
        G[from].push_back( mp(to,flow) );
        if(from==1)
            K+=flow;
    }

}

void ShowPath()
{
    for(int i=n;i!=1;i=ant[i].first)
    {
        g<<i<<' ';
    }
    g<<'\n';
}

int main()
{
    Read();
    g<<Edmonds();

    return 0;
}