#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>

#define INF 0x3f3f3f3f
#define Nmax 80
#define pb push_back
#define mp make_pair
#define super_start 70
#define super_sink 71

using namespace std;

struct muchie{
    int x,y;
    int cost;
    int capacity;
    int flux;
    muchie()
    {
        x = y = cost = capacity = flux = 0;
    }
};
bitset<Nmax> inQ;
queue<int> Q;
vector<muchie> edge;
vector<pair<int,int> > G[Nmax];
int GI[Nmax],GO[Nmax];
int DP[Nmax],daddy[Nmax],answer;

void insert_edge(int a,int b,int cap,int cst)
{
    muchie m;
    m.x = a;
    m.y = b;
    m.capacity = cap;
    m.cost = cst;
    G[a].pb(mp(b,edge.size()));
    edge.pb(m);
}
int N,M;

void read()
{
    scanf("%d%d",&N,&M);
    int a,b,c;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        GI[b]++;
        GO[a]++;
        insert_edge(a,b,INF,c);
        insert_edge(b,a,0,-c);
        answer += c;
    }
    for(int i = 1; i <= N; ++i)
    {
        if(GO[i] < GI[i])
        {
            insert_edge(super_start,i,GI[i]-GO[i],0);
            insert_edge(i,super_start,GI[i]-GO[i],0);
        }
        if(GO[i] > GI[i])
        {
            insert_edge(i,super_sink,GO[i]-GI[i],0);
            insert_edge(super_sink,i,GO[i]-GI[i],0);
        }
    }
}

bool bellman_ford()
{
    memset(DP,INF,sizeof(DP));DP[super_start] = 0;
    Q.push(super_start);
    int k;
    while(!Q.empty())
    {
        k = Q.front();Q.pop();inQ[k] = 0;
        if(k == super_sink) continue;
        for(vector<pair<int,int> >::iterator it = G[k].begin(); it != G[k].end(); ++it)
            if(DP[it->first] > DP[k] + edge[it->second].cost &&
               edge[it->second].capacity - edge[it->second].flux > 0)
            {
                DP[it->first] = DP[k] + edge[it->second].cost;
                daddy[it->first] = it->second;
                if(inQ[it->first])continue;
                inQ[it->first] = 1;
                Q.push(it->first);
            }
    }
    return (DP[super_sink] != INF);
}

void FLOW()
{
    int minCOST = 0, minFLOW, maxFLOW = 0;
    while(bellman_ford())
    {
        if(DP[super_sink] == INF) continue;
        minFLOW = INF;
        for(int nodc = super_sink; nodc != super_start; nodc = edge[daddy[nodc]].x + edge[daddy[nodc]].y - nodc)
            minFLOW = min(minFLOW,edge[daddy[nodc]].capacity - edge[daddy[nodc]].flux);
        if(!minFLOW)continue;
        for(int nodc = super_sink; nodc != super_start; nodc = edge[daddy[nodc]].x + edge[daddy[nodc]].y - nodc)
        {
            edge[daddy[nodc]].flux += minFLOW;
            edge[daddy[nodc]^1].flux -= minFLOW;
        }
        minCOST += minFLOW * DP[super_sink];
        maxFLOW += minFLOW;
    }
    answer += minCOST;
    printf("%d\n",answer);
}

int main()
{
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);

    read();
    FLOW();

    return 0;
}