#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define pii pair< int,int >
#define fs first
#define sc second
#define mp make_pair
#define N 70
#define pb push_back

int n;
const int sursa = 61, dest = 62;
int c[N][N];
vector< pii > a[N];
int degIn[N], degOut[N];
int rez;
int cost[N][N];
char marcat[N];
int t[N];
queue< int > q;
int d[N];

template <class T>
inline T minim(T x,T y) {
    return ( (x<y) ? x : y );
}

inline void citire() {
    int m;
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=0; i<m; ++i) {
        scanf("%d%d%d",&x,&y,&z);
        cost[x][y] = ( (cost[x][y]==0 || cost[x][y]>z) ? z : cost[x][y] );
        ++degIn[y];
        ++degOut[x];
        rez += z;
    }
}

inline void precalc() {
    for(int k=1; k<=n; ++k) {
        for(int i=1; i<=n; ++i) {
            if(i==k)
                continue;
            for(int j=1; j<=n; ++j) {
                if(j==k || j==i)
                    continue;
                if(cost[i][k]==0 || cost[k][j]==0)
                    continue;
                if(cost[i][j]==0 || (cost[i][k] + cost[k][j] < cost[i][j]))
                    cost[i][j] = cost[i][k] + cost[k][j];
            }
        }
    }

    for(int i=1; i<=n; ++i) {
        if(degIn[i]==degOut[i])
            continue;
        if(degIn[i]<degOut[i]) {
            marcat[i] = 1;
            a[i].pb(mp(dest,0));
            a[dest].pb(mp(i,0));
            c[i][dest] = degOut[i] - degIn[i];
            continue;
        }
        marcat[i] = 2;
        a[sursa].pb(mp(i,0));
        a[i].pb(mp(sursa,0));
        c[sursa][i] = degIn[i] - degOut[i];
    }

    for(int i=1; i<=n; ++i) {
        if(marcat[i]!=2)
            continue;
        for(int j=1; j<=n; ++j) {
            if(marcat[j]!=1)
                continue;
            a[i].pb(mp(j,cost[i][j]));
            a[j].pb(mp(i,-cost[i][j]));
            c[i][j] = N;
        }
    }
}

inline bool bellmanFord() {
    memset(t,0,sizeof(t));
    t[sursa] = -1;
    q.push(sursa);
    int now,next;
    d[sursa] = 0;
    int cost;

    while(!q.empty()) {
        now = q.front();
        q.pop();
        for(size_t i=0,lim=a[now].size(); i<lim; ++i) {
            next = a[now][i].fs;
            cost = a[now][i].sc;
            if(c[now][next]==0 || (t[next]!=0 && d[next]<=d[now]+cost))
                continue;
            t[next] = now;
            d[next] = d[now]+cost;
            q.push(next);
        }
    }

    if(t[dest]==0)
        return false;
    return true;
}
inline void flux() {
    int r,x;
    while(bellmanFord()) {
        r = N;
        x = dest;
        while(x!=sursa) {
            r = minim(r,c[t[x]][x]);
            x = t[x];
        }
        x = dest;
        while(x!=sursa) {
            c[t[x]][x] -= r;
            c[x][t[x]] += r;
            x = t[x];
        }
        rez += r*d[dest];
    }
}

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

    citire();
    precalc();
    flux();
    printf("%d\n",rez);
}