#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
 
ifstream cin("traseu.in");
ofstream cout("traseu.out");
 
int N, M;
const int nmax = 64, inf = int(1e9);
int dist[nmax][nmax];
int cap[nmax][nmax];
int f[nmax][nmax];
int dgIn[nmax], dgOut[nmax];
int bst[nmax];
int q[nmax*nmax];
bool inQ[nmax];
int T[nmax];
int src, sink;
int ans;
vector<int> G[nmax];
 
inline void readData() {
    cin>>N>>M;
    int a, b, c;
    for(int i = 0;i < M;i++) {
        cin>>a>>b>>c;
        a--, b--;
        dgOut[a]++;
        dgIn[b]++;
        dist[a][b] = c;
        dist[b][a] = -c;
        cap[a][b] = inf;
        G[a].push_back(b);
        G[b].push_back(a);
        ans += c;
    }
}
 
inline void buildGraph() {
    src = N;
    sink = N + 1;
    for(int i = 0;i < N;i++) {
        if(dgIn[i] > dgOut[i]) {
            cap[src][i] = dgIn[i] - dgOut[i];
            G[src].push_back(i);
        } else
        if(dgIn[i] < dgOut[i]) {
            cap[i][sink] = -dgIn[i] + dgOut[i];
            G[i].push_back(sink);
        }
    }
 
}
 
inline bool bellman() {
    int L, R;
    L = R = 0;
    for(int i = 0;i < N + 2;i++) {
        bst[i] = inf;
        T[i] = i;
        inQ[i] = false;
    }
    bst[src] = 0;
    q[R++] = src;
    inQ[src] = true;
    while(L < R) {
        int v = q[L++];
        inQ[v] = false;
        for(const int &w : G[v]) {
            if(f[v][w] < cap[v][w] && bst[w] > bst[v] + dist[v][w]) {
                bst[w] = bst[v] + dist[v][w];
                T[w] = v;
                if(inQ[w] == false) {
                    inQ[w] = true;
                    q[R++] = w;
                }
            }   
        }
    }
    return bst[sink] != inf;
}
 
int maxFlowMinCost() {
    int ret = 0;
    while(bellman()) {
        int fmin = inf;
        for(int v = sink;v != src;v = T[v]) {
            fmin = min(fmin,cap[T[v]][v] - f[T[v]][v]);
        }
        for(int v = sink;v != src;v = T[v]) {
            f[T[v]][v] += fmin;
            f[v][T[v]] -= fmin;
        }
        ret += fmin*bst[sink];
    }
    return ret;
}
 
int main()
{
    readData();
    buildGraph();
    ans += maxFlowMinCost();
    cout<<ans;
    return 0;
}