// http://infoarena.ro/problema/traseu
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define maxSize 62
#define oo 0x3f3f3f3f
#define source 0
#define destination 61

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

int nodes,edges;
int minCost;
bool visit[maxSize];
int dist[maxSize];
int father[maxSize];
int cost[maxSize][maxSize];
int capacity[maxSize][maxSize];
int gradeIn[maxSize],gradeOut[maxSize];
vector<int> graph[maxSize];

bool bellmanFord();

int main() {
	in >> nodes >> edges;

	int from,to,currentCost;
	for(int i=1;i<=edges;i++) {
		in >> from >> to >> currentCost;

		capacity[from][to] = oo;

		cost[from][to] = currentCost;
		cost[to][from] = -currentCost;

		gradeOut[from]++;
		gradeIn[to]++;

		graph[from].push_back(to);
		graph[to].push_back(from);

		minCost += currentCost;
	}

	for(int i=1;i<=nodes;i++)
		if(gradeIn[i] > gradeOut[i]) {
			graph[source].push_back(i);
			graph[i].push_back(source);

			capacity[source][i] = gradeIn[i] - gradeOut[i];
		}
		else 
			if(gradeOut[i] > gradeIn[i]) {
				graph[destination].push_back(i);
				graph[i].push_back(destination);
	
				capacity[i][destination] = gradeOut[i] - gradeIn[i];
			}

	while(bellmanFord()) {
		int node;
		int minFlow = oo;

		for(node=destination;node!=source;node=father[node])
			minFlow = min(minFlow,capacity[father[node]][node]);

		if(minFlow) {
			for(node=destination;node!=source;node=father[node]) {
				capacity[father[node]][node] -= minFlow;
				capacity[node][father[node]] += minFlow;
			}

			minCost += minFlow * dist[destination];
		}
	}

	out << minCost << "\n";

	in.close();
	out.close();

	return (0);
}

bool bellmanFord() {
	memset(dist,oo,sizeof(dist));
	dist[source] = 0;

	memset(visit,false,sizeof(visit));
	visit[source] = true;

	int node;
	vector<int>::iterator it,end;

	queue<int> myQueue;
	myQueue.push(source);

	while(!myQueue.empty()) {
		node = myQueue.front();
		myQueue.pop();

		end = graph[node].end();
		for(it=graph[node].begin();it!=end;++it)
			if(capacity[node][*it] > 0 && dist[node] + cost[node][*it] < dist[*it]) {
				dist[*it] = dist[node] + cost[node][*it];
				father[*it] = node;

				if(!visit[*it]) {
					visit[*it] = true;
					myQueue.push(*it);
				}
			}

		visit[node] = false;
	}

	if(dist[destination] != oo)
		return true;
	else
		return false;
}