#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;
}