#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
const int INF = 0x3f3f3f3f;
vector<int> G[100];
int C[100][100],Cs[100][100];
int son[100],inq[100],D[100],sou,dest;
int pr[100],ans;
queue<int> q;
int N,M;
int bf()
{
    for(int i=1; i<=dest; i++) D[i]=pr[i]=INF;
    D[sou]=0,q.push(sou),inq[sou]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        inq[x]=0;
        for(vector<int>::iterator it=G[x].begin(); it!=G[x].end(); ++it)
        {
            if(C[x][*it] && D[x]+Cs[x][*it] < D[*it])
            {
                D[*it]=D[x]+Cs[x][*it];
                pr[*it]=x;
                if(!inq[*it]) q.push(*it),inq[*it]=1;
            }
        }
    }
    return D[dest]<INF;
}
void addpath()
{
    int p=dest,m=INF;
    while(p!=sou) m=min(m,C[pr[p]][p]),p=pr[p];
    if(!m) return;
    p=dest;
    while(p!=sou)
    {
        C[pr[p]][p]-=m;
        ans += Cs[pr[p]][p]*m;
        C[p][pr[p]]+=m;
        p=pr[p];
    }
}
int main()
{
    fin>>N>>M;
    int x,y,c;
    for(int i=1; i<=M; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(y);
        G[y].push_back(x);
        Cs[x][y]=c,Cs[y][x]=-c;
        C[x][y]=INF,C[y][x]=0;
        son[x]++,son[y]--,ans+=c;
    }
    sou=N+1,dest=N+2;
    for(int i=1; i<=N; i++)
    {
        if(son[i]!=0)
        {
            G[sou].push_back(i);
            G[i].push_back(sou);
            G[i].push_back(dest);
            G[dest].push_back(i);
            if(son[i]<0) C[sou][i]+=-son[i];
            if(son[i]>0) C[i][dest]+=son[i];
        }
    }
    while(bf()) addpath();
    fout<<ans<<'\n';
    return 0;
}