/*
  Verified. 
  O(EV log V)
*/
#include<bits/stdc++.h>

#define INF (1<<29)
#define max_n 10000

using namespace std;

struct edge{int to,cap,rev;};


struct node_t{
  node_t *pp,*lp,*rp;
  int id,val,mini,minId,lazy;
  bool rev;
  edge *e;

  node_t(int id,int v):id(id),val(v),mini(v){
    pp=lp=rp=NULL;
    rev=false; 
    lazy=0; 
    update();
  }
   
  inline void update(){
    mini=val,minId=id;
    push();
    if(lp)lp->push();
    if(rp)rp->push();
    if(lp && mini>lp->mini)mini=lp->mini,minId=lp->minId;
    if(rp && mini>rp->mini)mini=rp->mini,minId=rp->minId;
  }
   
  inline void push(){
    if(rev){
      rev=false;
      swap(lp,rp);
      if(lp)lp->rev^=true;
      if(rp)rp->rev^=true;
    }
    if(lp)lp->lazy+=lazy;
    if(rp)rp->lazy+=lazy;

    val+=lazy,mini+=lazy,lazy=0;
  }
 
  inline bool is_root(){
    return !pp || (pp->lp != this && pp->rp != this);
  }
  
  inline void rotr(){
    node_t *q=pp,*r=q->pp;
    if((q->lp=rp))rp->pp=q;
    rp=q;q->pp=this;
    if((pp=r)){
      if(r->lp==q)r->lp=this;
      if(r->rp==q)r->rp=this;
    }
    q->update();
  }

  inline void rotl(){
    node_t *q=pp,*r=q->pp;
    if((q->rp=lp))lp->pp=q;
    lp=q;q->pp=this;
    if((pp=r)){
      if(r->lp==q)r->lp=this;
      if(r->rp==q)r->rp=this;
    }
    q->update();
  }

  inline void splay(){
    while(!is_root()){
      node_t *q=pp;
      node_t *r=q->pp;
      if(!q->is_root())r->push();
      q->push();
      push();
      if(q->is_root()){
	if(q->lp==this)rotr();
	else rotl();
      } else {
	if(r->lp==q){
	  if(q->lp==this){q->rotr();rotr();}
	  else {rotl();rotr();}
	} else {
	  if(q->rp==this){q->rotl();rotl();}
	  else {rotr();rotl();}
	}
      }
    }
    push();
    update();
  }
};

node_t *expose(node_t *x){
  node_t *rp=NULL;
  for(node_t *p=x;p;p=p->pp){
    p->splay();
    p->rp=rp;
    rp=p;
  }
  x->splay();
  return rp;
}

node_t *find_root(node_t *x){
  expose(x);
  while(x->lp)x=x->lp;
  return x;
}

void evert(node_t *p){
  expose(p);
  p->rev^=true;
}

void cut(node_t *c){
  expose(c);
  node_t *p=c->lp;
  c->lp=NULL;
  p->pp=NULL;
  c->val=INF;
}

void link(node_t *c,node_t *p){
  evert(c);
  c->pp=p;
}

void link(node_t *c,node_t *p,int val,edge *e){
  link(c,p);
  c->val=val;
  c->update();
  c->e=e;
}

//Verified.
int minId(node_t *x){expose(x); return x->minId;}
void add(node_t *x,int val){ expose(x); x->lazy=val; }

vector<edge> g[max_n];
 
void add_edge(int from,int to,int cap){
  g[from].push_back((edge){to,cap,g[to].size()});
  g[to].push_back((edge){from,0,g[from].size()-1});
}
 
int dist[max_n];

bool bfs(int s,int t){
  fill(dist,dist+max_n,-1);
  dist[s]=0;
  queue<int>que;
  que.push(s);
  while(!que.empty()){
    int u=que.front();que.pop();
    if(u==t)return true;
    for(int j=0;j<g[u].size();j++){
      edge e=g[u][j];
      if(dist[e.to]<0 && e.cap>0){
	dist[e.to]=dist[u]+1;
	que.push(e.to);
      }
    }
  }
  return false;
}

int n,ptr[max_n];
node_t *nodes[max_n];
vector<int>lists[max_n];

bool pour(int id,int i){
  int u=lists[id][i];
  if(find_root(nodes[u])==nodes[u])return true;
  edge *e=nodes[u]->e;
  expose(nodes[u]);
  int df=e->cap-nodes[u]->val;
  e->cap-=df;
  g[e->to][e->rev].cap+=df;
  return false;
}

int max_flow(int S,int T){
  int flow=0;
  while(bfs(S,T)){

    fill(ptr,ptr+max_n,0);
    for(int i=0;i<n;i++)nodes[i]=new node_t(i,INF);
    
    node_t *s=nodes[S],*t=nodes[T];
    for(int i=0;i<n;i++)lists[i].clear();
    
    while(true){
      node_t *v=find_root(s);

      if(v==t){
	expose(v=nodes[minId(s)]);
	flow+=v->mini;
	add(s,-v->mini);
	while(true){
	  expose(v=nodes[minId(s)]);
	  if(v->val>0)break;
	  g[v->e->to][v->e->rev].cap+=v->e->cap;
	  v->e->cap=0;
	  cut(v);
	}
	continue;
      } 
      
      if(ptr[v->id] < g[v->id].size()){
	edge &e=g[v->id][ptr[v->id]++];
	if(dist[e.to]==dist[v->id]+1 && e.cap>0){
	  link(v,nodes[e.to],e.cap,&e);
	  lists[e.to].push_back(v->id);
	} 
      } else {
	if(v==s){
	  for(int i=0;i<n;i++){
	    for(int j=0;j<lists[i].size();j++)pour(i,j);
	    lists[i].clear();
	  }
	  break;
	}
	for(int i=0;i<lists[v->id].size();i++){
	  if(!pour(v->id,i))cut(nodes[lists[v->id][i]]);
	}
	lists[v->id].clear();
      }
    }
  }
  return flow;
}

// AOJ GRL_6_A
int main(void){
  ios::sync_with_stdio(false);
  int e,a,b,c;
  cin >> n >> e;
  for(int i=0;i<e;i++){
    cin >> a >> b >> c;
    add_edge(a,b,c);
  }
 
  cout << max_flow(0,n-1) << endl;;
 
  return 0;
}

Measured memory_bytes: 1848