#include<fstream>
#include<vector>
using namespace std;
ifstream f("maxflow.in");
ofstream o("maxflow.out");
vector <int> a[1001];
vector <int> b[1001];

int parc[1000],val[1001],tata[1000],semn[1001],n,m,retea[1001][1001],flux[1001][1001],ok,c[10001];
void df(int nod,int v);
void dsf();

void marc(int nod,int father,int v){
//for(int i=1;i<=n;i++)o<<semn[i]<<" "; o<<endl;
//o<<endl;
//o<<nod<<endl;
//o<<endl;
if(semn[nod])flux[father][nod] += v;
else flux[nod][father] -= v;
if(father==1){
        for(int i=1;i<=n;i++)parc[i]=0;
       // ok=1;
       // df(1,1000000);
       dsf();
        }
else marc(father,tata[father],v);
}



void df(int nod,int v){
//if(nod!=1) val[nod] = v;
 //o<<v<<endl;
if(nod == n){
    ok=0;
    o<<"--"<<endl;
  //  for(int i=1;i<=n;i++)o<<semn[i]<<" "; o<<endl;
  //  for(int i=1;i<=n;i++)o<<tata[i]<<" "; o<<endl;
    marc(n,tata[n],v);
    return;
}
parc[nod]=1;
o<<"nod-"<<nod<<" "<<b[nod].size()<<endl;
for(int i=0;i<a[nod].size();i++){
    if(parc[a[nod][i]]!=1 && ok && flux[nod][a[nod][i]]<retea[nod][a[nod][i]]){
       tata[a[nod][i]]=nod;
       semn[a[nod][i]]=1;
     //  o<<"kk";
       df(a[nod][i],min(v,retea[nod][a[nod][i]]-flux[nod][a[nod][i]]));
    }
}
for(int i=0;i<b[nod].size();i++){
    if(parc[b[nod][i]]!=1 && flux[b[nod][i]][nod]>0 && ok && b[nod][i]!=1){
       tata[b[nod][i]]=nod;
       semn[b[nod][i]]=0;//ok=0;
     //  o<<b[nod][i]<<"--"<<endl;
   //   o<<"iii"<<endl; return;
       df(b[nod][i],min(v,flux[b[nod][i]][nod]));
    }
}
ok=0;
parc[nod]=0;
}
void dsf(){
int in = 0, sf = 0,nod;
c[0]=1;
while(in<=sf){
    nod = c[in];
        if(nod == n){
        //ok=0;
      //  o<<"--"<<val[nod]<<endl;
      //  for(int i=1;i<=n;i++)o<<semn[i]<<" "; o<<endl;
      //  for(int i=1;i<=n;i++)o<<tata[i]<<" "; o<<endl;
        marc(n,tata[n],val[nod]);
        return;
    }
    parc[nod]=1;
   // o<<"nod-"<<nod<<" "<<val[nod]<<endl;
    for(int i=0;i<a[nod].size();i++){
        if(parc[a[nod][i]]!=1 && flux[nod][a[nod][i]]<retea[nod][a[nod][i]]){
           tata[a[nod][i]]=nod;
           semn[a[nod][i]]=1;
         //  o<<"kk";
          // df(a[nod][i],min(v,retea[nod][a[nod][i]]-flux[nod][a[nod][i]]));
          sf++;
          c[sf]=a[nod][i];
          parc[a[nod][i]]=1;
          val[a[nod][i]]=min(val[nod],retea[nod][a[nod][i]]-flux[nod][a[nod][i]]);
        }
    }
    for(int i=0;i<b[nod].size();i++){
        if(parc[b[nod][i]]!=1 && flux[b[nod][i]][nod]>0  && b[nod][i]!=1){
           tata[b[nod][i]]=nod;
           semn[b[nod][i]]=0;//ok=0;
         //  o<<b[nod][i]<<"--"<<endl;
       //   o<<"iii"<<endl; return;
          // df(b[nod][i],min(v,flux[b[nod][i]][nod]));
          sf++;
          parc[b[nod][i]]=1;
          c[sf]=b[nod][i];
          val[b[nod][i]]=min(val[nod],flux[nod][b[nod][i]]);
        }
    }
    in++;
}
}
int main(){
f>>n>>m;
int x,y,z;
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)flux[i][j]=retea[i][j]=0;
for(int i=1;i<=m;i++){
    f>>x>>y>>z;
    a[x].push_back(y);
    b[y].push_back(x);
    retea[x][y] = z;
}
ok=1;
//o<<b[1].size()<<endl;
for(int i=1;i<=n;i++){
  //  for(int j=0;j<b[i].size();j++)o<<b[i][j]<<" ";
   // o<<endl;
}

//df(1,10000000);
val[1]=1000000;
dsf();


int f = 0;
for(int i=1;i<=n;i++)
{
//for(int j=1;j<=n;j++)o<<flux[i][j]<<" ";


//o<<endl;
}

for(int j=1;j<=n;j++)f+=flux[1][j];
o<<f;
}