max flow

#define ma 100010
ll dis[ma],pt[ma],n,s,t;
struct edge
{
 ll a,b,f,c;
};
vector<edge>e;
vector<ll>adj[ma];
void add_edge(ll a,ll b,ll c)
{
 edge e1;
 e1={a,b,0,c};
 adj[a].pb(e.sz);
 e.pb(e1);
 e1={b,a,0,c};
 adj[b].pb(e.sz);
 e.pb(e1);
}

bool bfs( )
{
 f(i,1,n+1)dis[i]=inf;
 queue<ll>q;
 q.push(s);
 dis[s]=0;
 while(q.sz>0)
 {
  ll u=q.front();q.pop();
  f(i,0,adj[u].sz)
  {
   ll id=adj[u][i];
   ll v=e[id].b;
   if(dis[v]==inf&&e[id].f<e[id].c)
   {
    dis[v]=dis[u]+1;
    q.push(v);
   }
  }
 }
 return dis[t]!=inf;
}



ll dfs(ll u,ll flow)
{
 if(!flow)return 0;
 if(u==t)return flow;
 for(;pt[u]<adj[u].sz;pt[u]++)
 {
  ll id=adj[u][pt[u]];
  ll v=e[id].b;
  if(dis[v]!=dis[u]+1)continue;
  ll pushed=dfs(v,min(flow,e[id].c-e[id].f));
  if(pushed)
  {
   e[id].f+=pushed;
   e[id^1].f-=pushed;
   return pushed;
  }
 }
 return 0;
}




ll dinic()
{
 ll flow=0;
 while(bfs())
 {
  mem(pt);
  while(ll pushed=dfs(s,inf))flow+=pushed;
 }
 return flow;
}


int main()
{
 ll m;
 cin>>n>>m;
 f(i,1,m+1)
 {
  ll u,v,c;
  cin>>u>>v>>c;
  add_edge(u,v,c);
 }
 s=1;
 t=n;
 ll ans=dinic();
 cout<<ans<<endl;
}