#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;
}