#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int kMaxN = 65;
const int kInf = 0x3f3f3f3f;

int N, M, in[kMaxN], out[kMaxN];
vector<pair<int, int>> G[kMaxN];
int cap[kMaxN][kMaxN], ans;

int dist[kMaxN], padre[kMaxN];
queue<int> q;
bool in_q[kMaxN];

void Link(int x, int y, int cost, int capacity) {
	G[x].emplace_back(y, cost);
	G[y].emplace_back(x, -cost);
	cap[x][y] = capacity;
}

void BuildGraph() {
	ifstream fin("traseu.in");
	fin >> N >> M;
	while (M--) {
		int x, y, c;
		fin >> x >> y >> c;
		++out[x];
		++in[y];
		Link(x, y, c, kInf);
		ans += c;
	}
	for (int i = 1; i <= N; ++i)
		if (in[i] > out[i])
			Link(0, i, 0, in[i] - out[i]);
		else if (in[i] < out[i])
			Link(i, N + 1, 0, out[i] - in[i]);
}

bool BellmanFord() {
	memset(dist, kInf, sizeof dist);
	dist[0] = 0;
	q.push(0);
	in_q[0] = true;
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		in_q[node] = false;
		for (auto it : G[node])
			if (cap[node][it.first] && dist[node] + it.second < dist[it.first]) {
				dist[it.first] = dist[node] + it.second;
				padre[it.first] = node;
				if (!in_q[it.first]) {
					q.push(it.first);
					in_q[it.first] = true;
				}
			}
	}
	return dist[N + 1] < kInf;
}

void Solve() {
	while (BellmanFord()) {
		int flow = kInf;
		for (int i = N + 1; i; i = padre[i])
			flow = min(flow, cap[padre[i]][i]);
		for (int i = N + 1; i; i = padre[i]) {
			cap[padre[i]][i] -= flow;
			cap[i][padre[i]] += flow;
		}
		ans += flow * dist[N + 1];
	}
}

int main() {
	BuildGraph();
	Solve();
	ofstream("traseu.out") << ans << "\n";
	return 0;
}