#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100, inf = 0x3f3f3f3f;

int N, M;
vector<int> G[NMAX], C[NMAX];
int in[NMAX], out[NMAX];
int dist[NMAX], rdist[NMAX];

struct flowEdge {
	int x, y, f, cap, cost;
	flowEdge *rev;
	flowEdge(int x, int y, int f, int cap, int cost, flowEdge *rev):
		x(x), y(y), f(f), cap(cap), cost(cost), rev(rev) {
	}
};
vector<flowEdge *> flowNetwork[NMAX];

void addEdge(int x, int y, int cap, int cost) {
	flowEdge *dir = new flowEdge(x, y, 0, cap, cost, 0);
	flowEdge *rev = new flowEdge(y, x, 0, 0, -cost, 0);
	dir->rev = rev;
	rev->rev = dir;
	flowNetwork[x].push_back(dir);
	flowNetwork[y].push_back(rev);
}

void graphDijkstra(int S, int *dist) {
	memset(dist, inf, (N + 1) * sizeof(int));
	priority_queue<pair<int, int>> Q;
	dist[S] = 0;
	Q.push({-dist[S], S});
	while (!Q.empty()) {
		auto now = Q.top();
		Q.pop();
		if (now.first != -dist[now.second])
			continue;
		for (int i = 0; i < int(G[now.second].size()); ++i) {
			if (dist[G[now.second][i]] > dist[now.second] + C[now.second][i]) {
				dist[G[now.second][i]] = dist[now.second] + C[now.second][i];
				Q.push({-dist[G[now.second][i]], G[now.second][i]});
			}
		}
	}
}

bool inQueue[NMAX];
void flowBellmanFord(int S, int *dist) {
	memset(dist, inf, (N + 3) * sizeof(int));
	queue<int> Q;
	Q.push(S);
	dist[S] = 0;
	inQueue[S] = 1;
	while (!Q.empty()) {
		int now = Q.front();
		Q.pop();
		inQueue[now] = 0;
		for (const auto &it: flowNetwork[now]) {
			if (it->f >= it->cap)
				continue;
			if (dist[it->y] > dist[now] + it->cost) {
				dist[it->y] = dist[now] + it->cost;
				if (!inQueue[it->y]) {
					Q.push(it->y);
					inQueue[it->y] = 1;
				}
			}
		}
	}
}

int temp[NMAX];
flowEdge *from[NMAX];
bool flowDijkstra(int S, int T, int *rdist) {
	memset(dist, inf, (N + 3) * sizeof(int));
	memset(temp, inf, (N + 3) * sizeof(int));
	priority_queue<pair<int, int>> Q;
	dist[S] = temp[S] = 0;
	Q.push({-dist[S], S});
	while (!Q.empty()) {
		auto now = Q.top();
		Q.pop();
		if (now.first != -dist[now.second])
			continue;
		for (const auto &it: flowNetwork[now.second]) {
			if (it->f >= it->cap)
				continue;
			if (dist[it->y] > dist[it->x] + rdist[it->x] - rdist[it->y] + it->cost) {
				dist[it->y] = dist[it->x] + rdist[it->x] - rdist[it->y] + it->cost;
				temp[it->y] = temp[it->x] + it->cost;
				from[it->y] = it;
				Q.push({-dist[it->y], it->y});
			}
		}
	}
	memcpy(rdist, temp, (N + 3) * sizeof(int));
	return rdist[T] != inf;
}

int maxFlowMinCost(int S, int T) {
	int flowCost = 0;
	flowBellmanFord(S, rdist);
	while (flowDijkstra(S, T, rdist)) {
		int augument = inf;
		flowEdge *curr = from[T];
		while (curr) {
			augument = min(augument, curr->cap - curr->f);
			curr = from[curr->x];
		}
		curr = from[T];
		while (curr) {
			curr->f += augument;
			curr->rev->f -= augument;
			curr = from[curr->x];
		}
		flowCost += augument * rdist[T];
	}
	return flowCost;
}

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

	int i, j;
	int x, y, z;
	int answer = 0;

	cin >> N >> M;
	for (i = 0; i < M; ++i) {
		cin >> x >> y >> z;
		G[x].push_back(y);
		C[x].push_back(z);
		answer += z;
		++out[x];
		++in[y];
	}

	int S = N + 1, T = N + 2;
	for (i = 1; i <= N; ++i) {
		if (in[i] == out[i])
			continue;
		if (in[i] > out[i])
			addEdge(S, i, in[i] - out[i], 0);
		else
			addEdge(i, T, out[i] - in[i], 0);
		graphDijkstra(i, dist);
		for (j = 1; j <= N; ++j) {
			if (i == j || in[j] == out[j])
				continue;
			addEdge(i, j, inf, dist[j]);
		}
	}

	answer += maxFlowMinCost(S, T);
	cout << answer << '\n';

	return 0;
}