#include <bits/stdc++.h>
using namespace std;
int cost[1005][1005],floc[1005][1005],tata[1005],n,m,ans=0;
bool viz[1005];
vector<int> adc[1005];
inline void zero()
{
    for(int i=1;i<=1000;++i)
        viz[i]=0;
}
bool bfs()
{
    zero();
    queue<int> q;
    viz[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<adc[t].size();++i)
            if(cost[t][adc[t][i]]!=floc[t][adc[t][i]] && !viz[adc[t][i]])
            {
                viz[adc[t][i]]=1;
                q.push(adc[t][i]);
                tata[adc[t][i]]=t;
                if(adc[t][i]==n)
                    return 1;
            }
    }
    return 0;
}
int main()
{
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        cost[x][y]+=z;
        adc[x].push_back(y);
        adc[y].push_back(x);
    }
    while(bfs())
    {
        int mi=INT_MAX;
        for(int i=n;i!=1;i=tata[i])
            mi=min(mi,cost[tata[i]][i]-floc[tata[i]][i]);
        for(int i=n;i!=1;i=tata[i])
            floc[tata[i]][i]+=mi,floc[i][tata[i]]-=mi;
        ans+=mi;
    }
    printf("%d",ans+1);
    return 0;
}