#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>

using namespace std;

ifstream cin("traseu.in");
ofstream cout("traseu.out");

const int MAXN = 65;
const int So = 0;
const int Si = 62;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

Graph G;
int N, M, Answer, Qu[MAXN][MAXN], F[MAXN][MAXN], C[MAXN][MAXN], inG[MAXN], outG[MAXN];
queue<int> Q;
bitset<MAXN>inQ;
vector<int> D(MAXN), Father(MAXN);

inline bool Bf(int Node) {
    for(fill(D.begin(), D.end(), oo), inQ.reset(), Q.push(So), D[So] = 0, inQ[So] = true ; !Q.empty() ; Q.pop(), Node = Q.front() ) {
        inQ[Node] = false;
        for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it)
            if(F[Node][*it] < Qu[Node][*it] && D[*it] > D[Node] + C[Node][*it]) {
                D[*it] = D[Node] + C[Node][*it];
                Father[*it] = Node;
                if(!inQ[*it]){
                    Q.push(*it);
                    inQ[*it] = true;
                }
            }
    }
    return D[Si] != oo;
}
int main() {
    cin >> N >> M;
    for(int i = 1 ; i <= M ; ++ i) {
        int x, y, z;
        cin >> x >> y >> z;
        Answer += z;
        ++outG[x];
        ++inG[y];
        G[x].push_back(y);
        G[y].push_back(x);
        Qu[x][y] = oo;
        C[x][y] = z;
        C[y][x] = -z;
    }
    for(int i = 1 ; i <= N ; ++ i)
        if(inG[i] > outG[i])
            G[So].push_back(i), Qu[So][i] = inG[i] - outG[i];
        else if(inG[i] < outG[i]) G[i].push_back(Si), Qu[i][Si] = outG[i] - inG[i];
    while(Bf(So)) {
        int MinFlow = oo;
        for(int i = Si ; i != So ; i = Father[i])
            MinFlow = min(MinFlow, Qu[Father[i]][i] - F[Father[i]][i]);
        for(int i = Si ; i != So ; i = Father[i])
            F[i][Father[i]] -= MinFlow,
            F[Father[i]][i] += MinFlow;
        Answer += MinFlow * D[Si];
    }
    cout << Answer << "\n";
    cin.close();
    cout.close();
    return 0;
}