#include <fstream>
#include <queue>

using namespace std;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

const int inf= 1<<30;
const int nmax= 60;

int in[nmax+1], out[nmax+1];
int cst[nmax+2][nmax+2], cpc[nmax+2][nmax+2];
vector <int> g[nmax+2];

bool inq[nmax+2];
queue <int> q;
int bf[nmax+2], p[nmax+2];

int bellmanford(int n){
    int src= 0, dest= n+1;
    for (int i= 1; i<=n+1; ++i){
        bf[i]= inf-1; p[i]= -1;
    }
    q.push(src); inq[src]= 1;

    while (!q.empty()){
        int x= q.front();
        q.pop(); inq[x]= 0;
        for (vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it){
            if (cpc[x][*it]>0&& bf[*it]>bf[x]+cst[x][*it]){
                bf[*it]= bf[x]+cst[x][*it];
                p[*it]= x;
                if (inq[*it]==0){
                    q.push(*it); inq[*it]= 1;
                }
            }
        }
    }

    return p[dest]!=-1;
}

int main(){
    int n, m;
    fin>>n>>m;
    for (int i= 1; i<=n; ++i){
        for (int j= 1; j<=n; ++j){
            if (i!=j){
                cst[i][j]= inf-1;
            }
        }
    }
    int sol= 0;
    for (int i= 1; i<=m; ++i){
        int x, y;
        fin>>x>>y;
        fin>>cst[x][y];
        sol+= cst[x][y];
        ++out[x]; ++in[y];
    }

    for (int i= 1; i<=n; ++i){
        for (int j= 1; j<=n; ++j){
            if (j!=i){
                for (int k= 1; k<=n; ++k){
                    if (k!=i&& k!=j&& cst[j][k]>cst[j][i]+cst[i][k]){
                        cst[j][k]= cst[j][i]+cst[i][k];
                    }
                }
            }
        }
    }

    int src= 0, dest= n+1;
    for (int i= 1; i<=n; ++i){
        if (in[i]>out[i]){
            g[i].push_back(src); g[src].push_back(i); 
            cpc[src][i]= in[i]-out[i]; 
        }else if (in[i]<out[i]){
            g[i].push_back(dest); g[dest].push_back(i);
            cpc[i][dest]= out[i]-in[i];
        }
    }
    for (int i= 1; i<=n; ++i){
        for (int j= 1; j<=n; ++j){
            if (in[i]>out[i]&& in[j]<out[j]){
                g[i].push_back(j); g[j].push_back(i);
                cpc[i][j]= inf;
                cst[j][i]= -cst[i][j];
            }
        }
    }

    while (bellmanford(n)){
        int mxf= inf;
        for (int i= dest; i!=src; i= p[i]){
            if (mxf>cpc[p[i]][i]){
                mxf= cpc[p[i]][i];
            }
        }
        sol+= mxf*bf[dest];
        for (int i= dest; i!=src; i= p[i]){
            cpc[p[i]][i]-= mxf;
            cpc[i][p[i]]+= mxf;
        }
    }

    fout<<sol<<"\n";
    return 0;
}