#include <bits/stdc++.h>
#define NMAX 70
#define SRC 0
#define SINK n+1
#define INF 2000000000
using namespace std;

ifstream fin("traseu.in");
ofstream fout("traseu.out");
int n,m,answer;
vector<int> g[NMAX];
vector<int> leftN,rightN;
pair<int,int> grad[NMAX];
int parent[NMAX];
int cost[NMAX][NMAX];
int costFlux[NMAX][NMAX],c[NMAX][NMAX],f[NMAX][NMAX];
bitset<NMAX> inQ;
int dist[NMAX];
queue<int> Q;
bool ok;

int cmcm() {
    fill(dist+SRC,dist+SINK+1,INF);
    inQ.reset();
    Q.push(SRC);
    dist[SRC]=0;
    inQ[SRC]=1;

    for(;Q.size();Q.pop()) {
        int aux=Q.front();
        inQ=0;

        for(auto q:g[aux]) {
            if(c[aux][q]-f[aux][q]>0&&dist[q]>dist[aux]+costFlux[aux][q]) {
                dist[q]=dist[aux]+costFlux[aux][q];
                parent[q]=aux;

                if(!inQ[q]) {
                    inQ[q]=1;
                    Q.push(q);
                }
            }
        }
    }

    if(dist[SINK]!=INF) {
        ok=1;
        int fMin=INF;
        for(int i=SINK;i!=SRC;i=parent[i]) {
            fMin=min(fMin,c[parent[i]][i]);
        }
        for(int i=SINK;i!=SRC;i=parent[i]) {
            f[parent[i]][i]+=fMin;
            f[i][parent[i]]-=fMin;
        }
        return fMin*dist[SINK];
    }
    return 0;
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++) {
        int x,y,z;
        fin>>x>>y>>z;
        grad[x].first++;
        grad[y].second++;
        cost[x][y]=z;
        answer+=z;
    }

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

    for(int i=1;i<=n;i++) {
        if(grad[i].first>grad[i].second) {
            g[i].push_back(SRC);
            g[SRC].push_back(i);
            c[SRC][i]=grad[i].first-grad[i].second;
            leftN.push_back(i);
        }
        else if(grad[i].second>grad[i].first) {
            g[i].push_back(SINK);
            g[SINK].push_back(i);
            c[i][SINK]=grad[i].second-grad[i].first;
            rightN.push_back(i);
        }
    }
    for(auto q:leftN) {
        for(auto w:rightN) {
            g[q].push_back(w);
            g[w].push_back(q);
            c[q][w]=INF;
            costFlux[q][w]=cost[q][w];
            costFlux[w][q]=-cost[q][w];
        }
    }
    ok=1;
    while(ok) {
        ok=0;
        answer+=cmcm();
    }
    fout<<answer;
    return 0;
}