//网络流SAP
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define N 1010
#define INF ((1<<30)-1)
int capacity[N][N];
int ac[N][N];
int level[N];
int m,n,ans;
int gap[N];
int pre[N];
queue<int> myq;
void BFS(int des)
{
memset(gap,0,sizeof(gap));
memset(level,-1,sizeof(level));
level[des]=0; gap[0]++;
while(!myq.empty())
myq.pop();
myq.push(des);
while(!myq.empty())
{
int index = myq.front();
myq.pop();
for(int i=1;i<=n;i++)
{
if(ac[index][i]>0&&level[i]==-1)
{
level[i]=level[index]+1;
gap[level[i]]++;
myq.push(i);
}
}
}
}
int SAP(int src,int des)
{
BFS(des); //level
memset(pre,-1,sizeof(pre));
pre[src]=src; //pre [src] =0 ; error
int sumflow=0;
int u=src,v;
int i;
while(level[src]<n)
{
for(v=1;v<=n;v++)
{
if(level[v]+1==level[u]&&capacity[u][v]>0)
{
break;
}
}
i=v;
//i
if(i<=n)
{
pre[i]=u;
u=i;
if(i==des)
{
int minflow=INF;
for(int j=des;j!=src;j=pre[j])
{
minflow=min(minflow,capacity[pre[j]][j]);
}
sumflow+=minflow;
for(int j=des;j!=src;j=pre[j])
{
capacity[pre[j]][j]-=minflow;
capacity[j][pre[j]]+=minflow;
}
u=src;
}
}
else//can't find a path from u
{
int min_level=des;
for(int j=1;j<=n;j++)
if(capacity[u][j]>0)
min_level=min(min_level,level[j]);
gap[level[u]]--;
if(gap[level[u]]==0) break;
level[u]=min_level+1;
gap[level[u]]++;
u=pre[u]; //back
}
}
return sumflow;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(capacity,0,sizeof(capacity));
memset(ac,0,sizeof(ac));
for(int i=1;i<=m;i++)
{
int u,v,c;
cin>>u>>v>>c;
if(u==v) continue; //
capacity[u][v]+=c; // += =
ac[v][u]+=c;
}
ans=SAP(1,n);
cout<<ans<<endl;
}
return 0;
}
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define N 1010
#define INF ((1<<30)-1)
int capacity[N][N];
int ac[N][N];
int level[N];
int m,n,ans;
int gap[N];
int pre[N];
queue<int> myq;
void BFS(int des)
{
memset(gap,0,sizeof(gap));
memset(level,-1,sizeof(level));
level[des]=0; gap[0]++;
while(!myq.empty())
myq.pop();
myq.push(des);
while(!myq.empty())
{
int index = myq.front();
myq.pop();
for(int i=1;i<=n;i++)
{
if(ac[index][i]>0&&level[i]==-1)
{
level[i]=level[index]+1;
gap[level[i]]++;
myq.push(i);
}
}
}
}
int SAP(int src,int des)
{
BFS(des); //level
memset(pre,-1,sizeof(pre));
pre[src]=src; //pre [src] =0 ; error
int sumflow=0;
int u=src,v;
int i;
while(level[src]<n)
{
for(v=1;v<=n;v++)
{
if(level[v]+1==level[u]&&capacity[u][v]>0)
{
break;
}
}
i=v;
//i
if(i<=n)
{
pre[i]=u;
u=i;
if(i==des)
{
int minflow=INF;
for(int j=des;j!=src;j=pre[j])
{
minflow=min(minflow,capacity[pre[j]][j]);
}
sumflow+=minflow;
for(int j=des;j!=src;j=pre[j])
{
capacity[pre[j]][j]-=minflow;
capacity[j][pre[j]]+=minflow;
}
u=src;
}
}
else//can't find a path from u
{
int min_level=des;
for(int j=1;j<=n;j++)
if(capacity[u][j]>0)
min_level=min(min_level,level[j]);
gap[level[u]]--;
if(gap[level[u]]==0) break;
level[u]=min_level+1;
gap[level[u]]++;
u=pre[u]; //back
}
}
return sumflow;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(capacity,0,sizeof(capacity));
memset(ac,0,sizeof(ac));
for(int i=1;i<=m;i++)
{
int u,v,c;
cin>>u>>v>>c;
if(u==v) continue; //
capacity[u][v]+=c; // += =
ac[v][u]+=c;
}
ans=SAP(1,n);
cout<<ans<<endl;
}
return 0;
}