#include<iostream> #include<cstdio> #include<cstring> #define INF 0x7fffffff using namespace std; struct data{int to,next,v;}e[402]; int n,m,ne=1,ans; int h[201],q[201],head[201]; void insert(int u,int v,int w) { ne++; e[ne].to=v;e[ne].v=w; e[ne].next=head[u]; head[u]=ne; ne++; e[ne].to=u; e[ne].next=head[v]; head[v]=ne; } bool bfs() { memset(h,-1,sizeof(h)); int t=0,w=1,i,now; q[0]=1;h[1]=0; while(t<w) { now=q[t++];i=head[now]; while(i) { if(e[i].v&&h[e[i].to]==-1) {h[e[i].to]=h[now]+1;q[w++]=e[i].to;} i=e[i].next; } } if(h[m]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==m)return f; int i=head[x],w,used=0; while(i) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(e[i].v,w)); used+=w; e[i].v-=w; e[i|1].v+=w; if(used==f)return f; } i=e[i].next; } if(!used)h[x]=-1; return used; } void dinic(){while(bfs())ans+=dfs(1,INF);} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } dinic(); printf("%d",ans); return 0; }