#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
typedef long long ll;
typedef pair<int,int> pi;
const int dim=1000+10;
int t,T;
int minim;
vector < int > viz(dim,0);
vector < int > V[dim];

bool BFS(int n,int sursa,int dest,vector < vector <int> >& C,vector < int >& T)
{
    queue < int > qu;
    qu.push(sursa);
    viz[sursa]=1;
    T[sursa]=-1;
    while(!qu.empty())
    {
        int nod=qu.front();
        qu.pop();
        viz[nod]=2;

        if(viz[dest])
            break;

        for(int j:V[nod])
            if(!viz[j] && C[nod][j])
            {
                viz[j]=1;
                T[j]=nod;
                qu.push((j));
            }
    }
    if(viz[dest])
        return true;
    return false;
}

void init(int n,vector < int >& T)
{
    for(int i=0;i<=n;i++)
        T[i]=-1,viz[i]=0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,sursa,dest;
    f>>n>>m;

    vector < vector < int > > C(n+1,vector<int>(n+1,0)),F(n+1,vector<int>(n+1,0));
    vector < vector < bool > > is(n+1,vector<bool>(n+1,0));
    vector < int > T(n+1,-1);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        V[a].pb(b);
        V[b].pb(a);
        is[a][b]=1;
        C[a][b]=c;
    }

    sursa=1;
    dest=n;
    while(BFS(n,sursa,dest,C,T)){

        for(int j:V[dest])
        if(viz[j] && C[j][dest])
        {
            T[dest]=j;
            int minim=INT_MAX;
            int tata=dest;
            while(tata!=sursa)
            {
                minim=min(minim,C[T[tata]][tata]);
                tata=T[tata];
            }

            tata=dest;
            while(tata!=sursa) //contruiesc graful rezidual din cel initial pentru urmatoarea iteratie
                        //actualizez si fluxul pe muchiile pe care merg
            {
                C[T[tata]][tata]-=minim;
                C[tata][T[tata]]+=minim;

                if(is[T[tata]][tata]==1) //exista muchia pe graful initial
                                        //am graful initial cu fluzurile si adun fluxul nou obtinut
                {
                    F[T[tata]][tata]+=minim;
                    F[tata][T[tata]]-=minim;
                }
                else
                {
                    F[T[tata]][tata]-=minim;
                    F[tata][T[tata]]+=minim;
                }
                tata=T[tata];
            }
        }
        init(n,T);
    }

    int ans=0;

    for(int nod:V[sursa])
        ans+=F[sursa][nod];
    g<<ans;

    return 0;
}