#include<fstream>
#include<queue>
#include<cstring>
#include<vector>
#define N 100
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("traseu.in");
ofstream g("traseu.out");
int x,y,c,i,m,n,mini,sumacost,t[N],d[N],cap[N][N],viz[N],gri[N],gre[N];
queue<int>q;
vector<pair<int,int> >v[N];
inline bool bfs()
{
    memset(t,0,sizeof(t));
    memset(d,INF,sizeof(d));
    memset(viz,0,sizeof(viz));
    viz[0]=1;
    d[0]=0;
    q.push(0);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        viz[x]=0;
        for(vector<pair<int,int> >::iterator it=v[x].begin();it!=v[x].end();++it)
        {
            if(d[it->first]>d[x]+it->second&&cap[x][it->first]>0)
            {
                t[it->first]=x;
                d[it->first]=d[x]+it->second;
                if(!viz[it->first])
                {
                    viz[it->first]=1;
                    q.push(it->first);
                }
            }
        }
    }
    return d[n+1]==INF;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,-c));
        ++gri[y];
        ++gre[x];
        cap[x][y]=INF;
        sumacost+=c;
    }
    for(i=1;i<=n;++i)
    {
        if(gri[i]>gre[i])
        {
            v[0].push_back(make_pair(i,0));
            v[i].push_back(make_pair(0,0));
            cap[0][i]=gri[i]-gre[i];
        }
        else
        if(gri[i]<gre[i])
        {
            v[n+1].push_back(make_pair(i,0));
            v[i].push_back(make_pair(n+1,0));
            cap[i][n+1]=gre[i]-gri[i];
        }
    }
    while(!bfs())
    {
        mini=INF;
        x=n+1;
        while(x)
        {
            mini=min(mini,cap[t[x]][x]);
            x=t[x];
        }
        if(mini==0)
        continue;
        x=n+1;
        while(x)
        {
            cap[t[x]][x]-=mini;
            cap[x][t[x]]+=mini;
            x=t[x];
        }
        sumacost+=mini*d[n+1];
    }
    g<<sumacost<<'\n';
    return 0;
}