#include<fstream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

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

#define NMAX 64
#define INF 1<<30

int N;int M; int S; int D;int C_T;

int grad[NMAX];int C[NMAX][NMAX];int F[NMAX][NMAX];int Cost[NMAX][NMAX];int From[NMAX];int dist[NMAX];

vector<int> G[NMAX];

bool s[NMAX];

void Read() {

    fin >>N>> M;

    S = 0; D = N + 1;
    for(int i = 1 ;i <= N; i++)
        for(int j = 1 ; j <= N; ++j)
            Cost[i][j] = 100000000;
    for(int i = 1; i <= M; ++i){
        int x, y, cost;

        fin >> x >> y>>cost;
        C_T += cost;
        Cost[x][y] = cost;
        grad[x]++;
        grad[y]--;
    }

}
void Roy(){

    for(int k = 1; k <= N; ++k)
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                if(i != k && j != k && Cost[i][j] > Cost[i][k] + Cost[k][j])
                    Cost[i][j] = Cost[i][k] + Cost[k][j];
}
bool BellmanFord(){

    for(int i = 0 ;i <= N + 1;++i) dist[i] = INF, s[i] = false,From[i] = -1;

    dist[0] = 0;
    queue <int> q;
    s[S] = true;
    From[S] = S;
    q.push(S);
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        s[nod] = false;

        //if(nod == D)continue;

        for(int i = 0 ;i < G[nod].size(); ++i){
            int x = G[nod][i];

            if(C[nod][x] - F[nod][x] >0 &&  dist[nod] + Cost[nod][x] < dist[x]){

                dist[x] = dist[nod] + Cost[nod][x];
                From[x] = nod;
                if(s[x] == false)
                q.push(x), s[x] = true;
            }
        }

    }
    return dist[D] != INF;
}
int flow(int S, int D){

    int Cost = 1;
    int rez = 0;
    for(rez = 0; BellmanFord() ; ){
            int fmin = INF;

            for(int j = D; j != S; j = From[j])
                fmin = min(fmin, C[From[j]][j] - F[From[j]][j]);

            for(int j = D; j != S; j = From[j])
                F[From[j]][j] += fmin, F[j][From[j]] -= fmin;
            rez += fmin * dist[D];
        }

    return rez;
}
int main(){

    Read();

    Roy();

    for(int i = 1; i <= N; ++i){

        if(!grad[i]) continue;
        if(grad[i] < 0){
            G[0].push_back(i);
            G[i].push_back(0);
            C[0][i] = -grad[i];

            for(int j = 1 ; j <= N; ++j)
                if(grad[j] > 0){
                    G[i].push_back(j);
                    G[j].push_back(i);
                    C[i][j] = INF;
                    Cost[j][i] = -Cost[i][j];
                }
            continue;
        }

        G[D].push_back(i);
        G[i].push_back(D);
        C[i][D] = grad[i];
    }
    fout <<C_T + flow(0, D);

    return 0;
}