#include <iostream> #include <cstdlib> #include <stdio.h> #include <map> #include <cstring> #include <math.h> #include <stdlib.h> #define ll long long #define INF 0x3f3f3f3f #define cle(a) memset(a,0,sizeof(a)) using namespace std; struct G{ int v,cap,next; }E[600010]; int pre[1100],l,d[1100],p[1100]; int Q[1100]; void init(){ l=0; memset(pre,-1,sizeof pre); } void add(int u,int v,int cap){ E[l].v=v; E[l].cap=cap; E[l].next=pre[u]; pre[u]=l++; } bool bfs(int s,int e,int n){ int i,u,v,head,tail; for(i=0;i<=n;i++)d[i]=-1; head=tail=0; d[s]=0; Q[tail]=s; while(head<=tail){ u=Q[head++]; for(i=pre[u];i+1;i=E[i].next){ v=E[i].v; if(d[v]==-1&&E[i].cap>0){ d[v]=d[u]+1; Q[++tail]=v; } } } return (d[e]!=-1); } int dfs(int u,int &e,int f){ if(u==e||f==0)return f; int flow=0,tmp; for(;p[u]+1;p[u]=E[p[u]].next){ G& en=E[p[u]]; if(d[u]+1==d[en.v]){ tmp=dfs(en.v,e,min(f,en.cap)); if(tmp>0){ en.cap-=tmp; E[p[u]^1].cap+=tmp; flow+=tmp; f-=tmp; if(f==0)break; } } } return flow; } int dinic(int s,int e,int n){ int i,ans=0; while(bfs(s,e,n)){ for(i=0;i<=n;i++)p[i]=pre[i]; ans+=dfs(s,e,INF); } return ans; } int x,y,w; int main() { int n,m; while(cin>>m>>n){ init(); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&w); add(x,y,w); add(y,x,0); } printf("%d\n",dinic(1,n,n)); //源点1汇点n } return 0; }