#include<iostream>
#include<queue>
using namespace std;
struct Map
{
int f,c;
}map[201][201];
int pre[201],v[201];
queue<int>q;
int n,m,a,b,c,s=1;
int main()
{
while(cin>>n>>m)
{
int i,j;
memset(map,0,sizeof(map));
while(n--)
{
cin>>a>>b>>c;
map[a][b].c+=c;
}
while(1)
{
memset(pre,0,sizeof(pre));
v[s]=0x7fffffff;
pre[s]=s;
while(!q.empty())
q.pop();
q.push(s);
while(!q.empty()&&pre[m]==0)
{
i=q.front();
q.pop();
for(j=1;j<=m;j++)
{
if(pre[j]==0)
{
if(map[i][j].f<map[i][j].c)
{
v[j]=min(v[i],map[i][j].c-map[i][j].f);
pre[j]=i;
q.push(j);
}
else if(map[j][i].f>0)
{
v[j]=min(v[i],map[j][i].f);
pre[j]=-1*i;
q.push(j);
}
}
}
}
if(pre[m]==0)
break;
i=m;
while(i!=s)
{
j=abs(pre[i]);
if(pre[i]>0)
{
map[j][i].f+=v[m];
}
else
{
map[i][j].f-=v[m];
}
i=j;
}
}
int ans=0;
for(i=1;i<=m;i++)
{
if(i!=s)
ans+=map[s][i].f;
}
cout<<ans<<endl;
}
system("pause");
return 0;
}