#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

const int N = 65;
const int INF = 1e9;

int n, m, maxSize, source, sink;
int minCost, maxFlux;
int t[N], cap[N][N], flow[N][N], cost[N][N], gradInt[N], gradExt[N];
vector<int> g[N], realDist, newRealDist, positiveDist;
vector<bool> vizitat;

void BellmanFord()
{
	vector<bool> inCoada(maxSize, false);
	realDist.assign(maxSize, INF);

	queue<int> coada;
	coada.push(source);
	inCoada[source] = true;
	realDist[source] = 0;

	while (!coada.empty())
	{
		int x = coada.front();
		coada.pop();
		inCoada[x] = false;

		for (int y : g[x])
		{
			if (flow[x][y] != cap[x][y] && realDist[x] + cost[x][y] < realDist[y])
			{
				t[y] = x;
				realDist[y] = realDist[x] + cost[x][y];
				
				if (!inCoada[y])
				{
					coada.push(y);
					inCoada[y] = true;
				}
			}
		}
	}
}

void Dijkstra()
{
	positiveDist.assign(maxSize, INF);
	newRealDist.assign(maxSize, INF);
	vizitat.assign(maxSize, false);

	positiveDist[source] = newRealDist[source] = 0;

	priority_queue<pair<int, int>> heap;
	heap.push({ 0, source });

	while (!heap.empty())
	{
		int x = heap.top().second;
		heap.pop();

		if (vizitat[x])
			continue;

		vizitat[x] = true;

		for (int y : g[x])
		{
			int positiveCostXY = realDist[x] + cost[x][y] - realDist[y];

			if (!vizitat[y] && flow[x][y] != cap[x][y] && positiveDist[x] + positiveCostXY < positiveDist[y])
			{
				positiveDist[y] = positiveDist[x] + positiveCostXY;
				heap.push({ -positiveDist[y], y });
				newRealDist[y] = newRealDist[x] + cost[x][y];
				t[y] = x;
			}
		}
	}

	realDist = newRealDist;
}

void MaxFluxMinCost()
{
	BellmanFord();

	while (true)
	{
		Dijkstra();

		if (positiveDist[sink] == INF)
			break;

		int minFlux = 1 << 30;
		for (int node = sink; node != source; node = t[node])
			minFlux = min(minFlux, cap[t[node]][node] - flow[t[node]][node]);

		minCost += realDist[sink] * minFlux;
		maxFlux += minFlux;

		for (int node = sink; node != source; node = t[node])
		{
			flow[t[node]][node] += minFlux;
			flow[node][t[node]] -= minFlux;
		}
	}
}

void AddEdge(int x, int y, int capacitate, int pret)
{
	g[x].push_back(y);
	g[y].push_back(x);
	cap[x][y] = capacitate;
	cost[x][y] = pret;
	cost[y][x] = -pret;
}

int main()
{
	fin >> n >> m;
	source = 0;
	sink = n + 1;
	maxSize = sink + 1;
	
	int ans = 0;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		AddEdge(x, y, INF, c);
		ans += c;

		gradExt[x]++;
		gradInt[y]++;
	}

	for (int i = 1; i <= n; i++)
	{
		if (gradInt[i] > gradExt[i])
			AddEdge(source, i, gradInt[i] - gradExt[i], 0);
		else if (gradExt[i] > gradInt[i])
			AddEdge(i, sink, gradExt[i] - gradInt[i], 0);
	}

	MaxFluxMinCost();
	fout << ans + minCost;
}