#include <cstdio>
#include <set>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_N = 65;

const int source = 0;
const int dest = 64;
const int INF = 0x7f7f7f7f;
const int off = 1;

vector<int> G[MAX_N*off];

int cost[MAX_N*off][MAX_N*off];
int in_deg[MAX_N];
int out_deg[MAX_N];
int best[MAX_N*off];
int C[MAX_N*off][MAX_N*off];
int TT[MAX_N*off];
bool in_Q[MAX_N*off];
int n,m;


struct comp{
    bool operator() (const int &a,const int &b){
        return cost[a] == cost[b] ? a > b : cost[a] > cost[b];
    }
};

set<int,comp> T;

void roy()
{
    int i,j,k;
    for(k = 1 ; k <= n ; ++ k)
        for(i = 1 ; i <= n ; ++ i)
            for(j = 1 ; j <= n ; ++ j){
                if(cost[i][k] == INF || cost[k][j] == INF)continue;
                cost[i][j] = min(cost[i][j] , cost[i][k] + cost[k][j]);
            }

}


bool dij()
{
    memset(best,0x7f,sizeof(best));
    memset(in_Q,0,sizeof(in_Q));
    T.clear();
    best[source] = 0;
    T.insert(source);
    int nod;
    while(!T.empty()){
        nod = *T.begin();
        T.erase(T.begin());
        in_Q[nod] = 0;
        for(auto it = G[nod].begin() ; it != G[nod].end() ; ++ it){
            if(C[nod][*it] == 0)continue;
            if(best[nod] + cost[nod][*it] < best[*it]){
                if(in_Q[*it])
                    T.erase(*it);
                in_Q[*it] = 1;
                best[*it] = best[nod] + cost[nod][*it];
                TT[*it] = nod;
                T.insert(*it);
            }
        }
    }

    return best[dest] != INF;

}

int flow()
{
    int nod,flux = 0,cost_flux = 0,f_min;
    while(dij()){
        f_min = INF;
        for(nod = dest ; nod ; nod = TT[nod])
            f_min = min(f_min,C[TT[nod]][nod]);

        flux += f_min;
        cost_flux += best[dest] * f_min;

        for(nod = dest ; nod ; nod = TT[nod]){
            C[TT[nod]][nod] -= f_min;
            C[nod][TT[nod]] += f_min;
        }

    }

    return cost_flux;
}

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

    int i,from,to,len,total = 0;

    scanf("%d %d",&n,&m);

    memset(&cost[0][0],0x7f,sizeof(cost));

    while(m--){
        scanf("%d %d %d",&from,&to,&len);
        cost[from][to] = len;
        total += len;
        out_deg[from]++;
        in_deg[to]++;
    }

    roy();


    for(i = 1 ; i <= n ; ++ i){
        if(in_deg[i] == out_deg[i])continue;
        if(in_deg[i] > out_deg[i]){
            C[source][i] = in_deg[i] - out_deg[i];
            G[source].push_back(i);
            cost[source][i] = cost[i][source] = 0;
            G[i].push_back(source);
        }else{
            G[i].push_back(dest);
            G[dest].push_back(i);
            cost[dest][i] = cost[i][dest] = 0;
            C[i][dest] = out_deg[i] - in_deg[i];
        }
    }

    for(auto it1 = G[source].begin() ; it1 != G[source].end() ; ++ it1)
        for(auto it2 = G[dest].begin() ; it2 != G[dest].end() ; ++ it2){
            if(cost[*it1][*it2] >= INF)continue;
            G[*it1].push_back(*it2);
            G[*it2].push_back(*it1);
            C[*it1][*it2] = INF;

            cost[*it1][*it2] = cost[*it1][*it2];
            cost[*it2][*it1] = -cost[*it1][*it2];
        }

    total += flow();
    printf("%d\n",total);
}