#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

#define ITERATOR vector < pair <int, int> >::iterator
const int NMAX = 70, INF = 0x3f3f3f3f;

int n, SOURCE, DEST;
int in[NMAX], out[NMAX], cap[NMAX][NMAX], flow[NMAX][NMAX], dad[NMAX];
bool vis[NMAX];
vector < pair <int, int> > graph[NMAX];
int dmin[NMAX];

void drawEdge (int a, int b, int costAB, int capAB) {
    graph[a].push_back(make_pair(b, costAB));
    graph[b].push_back(make_pair(a, -costAB));
    cap[a][b] = capAB;    
}

bool bellmanFord () {
    int i, node;
    queue <int> q; 
    memset(dmin, INF, sizeof(dmin));

    q.push(SOURCE);
    vis[SOURCE] = 1;
    dmin[SOURCE] = 0;
    while(!q.empty()) {
        node = q.front();
        vis[node] = 0;
        q.pop();
        
        for(ITERATOR it = graph[node].begin(); it != graph[node].end(); ++ it) 
            if(flow[node][it->first] < cap[node][it->first] && dmin[node] + it->second < dmin[it->first]) {
                dmin[it->first] = dmin[node] + it->second;
                dad[it->first] = node;

                if(!vis[it->first]) {
                    vis[it->first] = 1;
                    q.push(it->first);
                }
            }
    }

    if(dmin[DEST] < INF)
        return 1;
    return 0;
}

int maxFlow() {
    int node, minFlow, res;

    res = 0;
    while(bellmanFord()) {
        node = DEST;
        minFlow = INF;
        while(node != SOURCE) {
            minFlow = min(minFlow, cap[dad[node]][node] - flow[dad[node]][node]);
            node = dad[node];
        }

        node = DEST;
        while(node != SOURCE) {
            flow[dad[node]][node] += minFlow;
            flow[node][dad[node]] -= minFlow;
            node = dad[node];
        }

        res += dmin[DEST] * minFlow;
    }
    
    return res;
}

int main() {
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);
    int cost, m, i, j, x, y, ans;

    scanf("%d%d", &n, &m);
    ans = 0;
    for(i = 1; i <= m; ++ i) {
        scanf("%d%d", &x, &y);
        scanf("%d", &cost);

        ++ out[x];
        ++ in[y];
        ans += cost;
        
        drawEdge(x, y, cost, INF);
    }


    SOURCE = 0;
    DEST = n + 1;
    
    for(i = 1; i <= n; ++ i)
        if(in[i] > out[i])
            drawEdge(SOURCE, i, 0, in[i] - out[i]);

    for(i = 1; i <= n; ++ i)
        if(in[i] < out[i])
            drawEdge(i, DEST, 0, out[i] - in[i]);

    ans += maxFlow();

    printf("%d\n", ans);
    return 0;
}