#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

#define pb push_back
#define sz size()
#define MP make_pair
#define ff first
#define ss second

#define NMAX 100
#define INFI 0x3f3f3f3f

int n, m;
int source, sink;
int in[NMAX], out[NMAX];
int muchie[NMAX][NMAX];
int cap[NMAX][NMAX];
int dist[NMAX][NMAX];
int cost[NMAX][NMAX];
int res;

void read()
{
    memset(muchie, INFI, sizeof(muchie));
    scanf("%d %d", &n, &m);
    for(int i = 0, x, y, z; i < m; ++i)
       scanf("%d %d %d", &x, &y, &z), res += z, muchie[x][y] = z, out[x]++, in[y]++;
}

void bfcost(int s, int dist[NMAX])
{
    int i, x;
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        x = q.front(), q.pop();
        for(i = 1; i <= n; ++i)
            if(dist[i] > dist[x] + muchie[x][i])
            {
                dist[i] = dist[x] + muchie[x][i];
                q.push(i);
            }
    }
    //printf("%d: ", s); for(i = 1; i <= n; ++i) printf("%d ", dist[i]); printf("\n");
}
vector<int> first, second;

void form()
{
    memset(cost, 0, sizeof(cost));
    vector<int> :: iterator it, other;
    source = 0;
    sink = n+1;
    memset(cap, 0, sizeof(cap));
    vector<int> first, second;
    for(int i = 1; i <= n; ++i)
        if(out[i] > in[i])
            second.pb(i);
        else if(in[i] > out[i])
            first.pb(i);

    for(it = first.begin(); it != first.end(); ++it)
    {
        cost[source][*it] = 0;
        cost[*it][source] = 0;
        cap[source][*it] = in[*it] - out[*it];
        for(other = second.begin(); other != second.end(); ++other)
        {
            cap[*it][*other] = INFI;
            cost[*other][*it] = -dist[*it][*other];
            cost[*it][*other] = dist[*it][*other];
        }
    }
    for(it = second.begin(); it != second.end(); ++it)
    {
        cap[*it][sink] = out[*it] - in[*it];
        cost[*it][sink] = 0;
        cost[sink][*it] = 0;
    }
}

inline int MIN(int a, int b) { return (a < b) ? (a) : (b); }

int bf()
{
    int dist[NMAX], t[NMAX];
    queue<int> q;
    int i, x;
    q.push(source);
    memset(dist, INFI, sizeof(dist));
    memset(t, 0, sizeof(t));
    dist[source] = 0;
    while(!q.empty())
    {
        x = q.front(), q.pop();
        for(i = source; i <= sink; ++i)
            if(cap[x][i] && dist[i] > dist[x] + cost[x][i])
            {
                t[i] = x;
                dist[i] = dist[x] + cost[x][i];
                q.push(i);
            }
    }
    
    if(dist[sink] == INFI) return -1;
    int _min = INFI;
    for(i = sink; i != source; i = t[i])
        _min = MIN(_min, cap[t[i]][i]);

    for(i = sink; i != source; i = t[i])
        cap[t[i]][i] -= _min, cap[i][t[i]] += _min;
    return _min * dist[sink];
}

int main()
{
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);
    
    read();
    
    memset(dist, INFI, sizeof(dist));
    for(int i = 1; i <= n; ++i)
        bfcost(i, dist[i]);

    form();

    int aux;
    while(1)
    {
        aux = bf();
        //printf("%d\n", aux);
        if(aux == -1) break;
        res += aux;
    }
    printf("%d\n", res);
    
    return 0;
}