#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int DN=1005;
int n,m,f,g,s,d;
int dist[DN],viz[DN],pr[DN],c[DN][DN],flow[DN][DN],lst;
int cnt=0;
long long  sol;
vector<int >v[DN];
priority_queue<int>q;

int r[DN],h[DN];
set<int>sett;



void pompare(int f,int g)
{
    cnt++;
    int val=c[f][g]-flow[f][g];
    //if(c[f][g]==-1)
      //  return;
    //if(c[f][g]==0)
      //  val=flow[g][f];
    //cout<<"zxzczx "<<val<<'\n';
    val=min(val,r[f]);
    val=max(val,0);
    //cout<<c[f][g]<<'\n';
   // if(c[f][g])
    {
        flow[f][g]+=val;
        //if(flow[f][g]==c[f][g])
          //  c[f][g]=0;
    }
    //else
        flow[g][f]-=val;
    r[f]-=val;
    r[g]+=val;
    lst=val;
    //if(c[f][g]==0)
      //  c[f][g]=c[g][f]=-1;
    //cout<<f<<' '<<g<<' 'r[f]<<' '<<r[g]<<'\n';

}

int inaltare(int nod)
{
    cnt++;
    if(nod==s||nod==d)
        return 0;

    for(auto i:v[nod])
    {
        if(flow[nod][i]>=c[nod][i])
            continue;
        if(c[nod][i]==-1||c[i][nod]==-1)
            continue;

        if(h[nod]>h[i])
            return 0;
    }

    int t=n+1;
    int zz=0;
    for(auto i:v[nod])
    {
        if(flow[nod][i]>=c[nod][i])
            continue;
        if(c[nod][i]==-1||c[i][nod]==-1)
            continue;

        t=min(t,h[i]+1);
        zz=1;
    }
    //cout<<nod<<' '<<t<<' '<<r[d]<<'\n';
    //h[nod]=t;
    //cout<<nod<<' '<<t<<'\n';
    if(t==n+1)
        return 0;
    h[nod]=t;
    return 1;
}

int upd(int nod)
{
    int vf=0;

        //cout<<'z'<<' '<<nod<<' '<<r[nod]<<' '<<r[d]<<'\n';

        for(auto i:v[nod])
        {
            if(h[nod]!=h[i]+1)
                continue;

            if(flow[nod][i]>=c[nod][i])
                continue;

            if(c[nod][i]==-1||c[i][nod]==-1)
            continue;

            pompare(nod,i);
            //cout<<"sfdsf"<<' '<<h[nod]<<' '<<h[i]<<'\n';
            if(lst!=0)
            vf=1;
        }
    return vf;
}

void solve()
{
    h[s]=n;
    for(auto i:v[s])
    {
        r[s]-=c[s][i];
        flow[s][i]=c[s][i];
        r[i]=c[s][i];
    }

    int vf=1;
    while(vf&&cnt<1e6)
    {
        //cout<<vf<<'\n';
        vf=0;
        int nod=s;

        for(nod=s;nod<=d;nod++)
        {
            if(nod==s||nod==d)
                continue;
          //  cout<<'z'<<nod<<'\n';
            if(r[nod]<=0)
                continue;
            //vf=inaltare(nod);
            //if(vf)
              //  break;

            vf=max(vf,upd(nod));
      //      cout<<"tttt "<<vf<<' '<<nod<<' '<<r[nod]<<' '<<h[nod]<<' '<<r[d]<<'\n';
        }
        //cout<<vf<<'\n';
      if(vf)
            continue;
        for(nod=s;nod<=d;nod++)
        {
            if(nod==s||nod==d)
                continue;
            //cout<<nod<<'\n';
            if(r[nod]<=0)
                continue;
            vf=max(vf,inaltare(nod));

        }

        //cout<<'z'<<' '<<vf<<'\n';
    }
    sol=r[d];
}


int main()
{
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g;
        fin>>c[f][g];
        v[f].pb(g);
        v[g].pb(f);
    }

    s=1;
    d=n;
    //s--;
    //d--;

    solve();
    //for(int i=1;i<=n;i++)
      //  cout<<r[i]<<' ';
    fout<<sol;
}