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

using namespace std;

const int inf = 1000000000;
int n, m, dp [65][65], grad_int [65], grad_ext [65], c [65][65], ans = 0;
int f [65][65], father [65], l [65];
bool used [65];
vector <int> graph [65];
queue <int> q;

void init () {
    int i, j;
    for (i = 1; i <= n; i ++) {
        for (j = 1; j <= n; j ++)
            if (dp [i][j] == 0)
                dp [i][j] = inf;
    }
}

bool bellman_ford () {
    int i, x;
    vector <int> :: iterator it;

    memset (used, 0, sizeof (used));
    father [0] = -2;
    used [0] = 1;
    q.push (0);
    l [0] = 0;
    for (i = 1; i <= n + 1; i ++)
        father [i] = -1, l [i] = inf;
    while (!q.empty ()) {
        x = q.front ();
        used [x] = 0;
        q.pop ();
        for (it = graph [x].begin (); it != graph [x].end (); ++ it)
            if (c [x][*it] - f [x][*it] > 0 && l [*it] > l [x] + dp [x][*it]) {
                l [*it] = l [x] + dp [x][*it];
                father [*it] = x;
                if (!used [*it]) {
                    used [*it] = 1;
                    q.push (*it);
                }
            }
    }
    if (l [n + 1] == inf)
        return false;
    return true;
}

void read () {
    int i, x, y, c1;

    init ();
    scanf ("%d%d", &n, &m);
    init ();
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d%d", &x, &y, &c1);
        ans = ans + c1;
        grad_ext [x] ++;
        grad_int [y] ++;
        dp [x][y] = c1;
    }
}

void roy_floyd () {
    int i, j, k;

    for (k = 1; k <= n; k ++)
        for (i = 1; i <= n; i ++)
            for (j = 1; j <= n; j ++)
                dp [i][j] = min (dp [i][j], dp [i][k] + dp [k][j]);
}

void solve () {
    int i, j, min, flow = 0, s, d;

    roy_floyd ();
    for (i = 1; i <= n; i ++)
        if (grad_int [i] > grad_ext [i]) {
            c [0][i] = grad_int [i] - grad_ext [i];
            graph [0].push_back (i);
            graph [i].push_back (0);
        }
        else
            if (grad_ext [i] > grad_int [i]) {
                graph [i].push_back (n + 1);
                graph [n + 1].push_back (i);
                c [i][n + 1] = grad_ext [i] - grad_int [i];
            }

    for (i = 1; i <= n; i ++)
        for (j = 1; j <= n; j ++)
            if (i != j && grad_ext [i] < grad_int [i] && grad_int [j] < grad_ext [j]) {
                c [i][j] = inf;
                dp [j][i] = - dp [i][j];
                graph [i].push_back (j);
                graph [j].push_back (i);
            }
    s = 0;
    d = n + 1;
    while (bellman_ford ()){
        min = inf;
        for (i = d; i != s; i = father [i])
            if (min > c [father [i]][i] - f [father [i]][i])
                min = c [father [i]][i] - f [father [i]][i];
        if (min == 0)
            continue;
        for (i = d; i != s; i = father [i]) {
            f [father [i]][i] += min;
            f [i][father [i]] -= min;
        }
        flow = flow + min * l [d];
    }
    printf ("%d\n", ans + flow);
}

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

    read ();
    solve ();
    return 0;
}