#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "traseu";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;


vector<int> inDeg;
vector<int> outDeg;
vector<vector<int> > RF;

vector<int> lefts;
vector<int> rights;

int MinCost;
int N, M;


vector<vector<int> > Flux;
vector<vector<int> > Cost;
vector<vector<int> > Cap;
vector<vector<int> > G;


bool Bellman()
{
	vector<int> pred(N + 2, -1);
	vector<int> dist(N + 2, INF);
	vector<bool> inQ(N + 2);
	queue<int> Q;
	Q.push(0);
	inQ[0] = true;
	dist[0] = 0;
	while(Q.empty() == false)
	{
		int c = Q.front();
		Q.pop();
		inQ[c] = false;
		for(vector<int>::iterator itr = G[c].begin();
			itr != G[c].end();
			itr++)
		{
			if(Cap[c][*itr] - Flux[c][*itr] > 0)
			{
				if(dist[*itr] > dist[c] + Cost[c][*itr])
				{
					dist[*itr] = dist[c] + Cost[c][*itr];
					pred[*itr] = c;
					if(inQ[*itr] == false)
					{
						inQ[*itr] = true;
						Q.push(*itr);
					}
				}
			}
		}
	}

	if(pred[N+1] == -1)
	{
		return false;
	}


	int maxFlow = INF;
	for(int c = N + 1; c != 0; c = pred[c])
	{
		maxFlow = min(maxFlow, Cap[pred[c]][c] - Flux[pred[c]][c]);
	}

	for(int c = N + 1; c != 0; c = pred[c])
	{
		Flux[pred[c]][c] += maxFlow;
		Flux[c][pred[c]] -= maxFlow;
	}

	MinCost += maxFlow * dist[N+1];

	return true;
}


int main()
{
	fstream fin(infile.c_str(), ios::in);
	fin >> N >> M;
	RF.resize(N + 1, vector<int>(N + 1, INF));
	inDeg.resize(N + 1);
	outDeg.resize(N + 1);


	Flux.resize(N + 2, vector<int>(N + 2));
	Cost.resize(N + 2, vector<int>(N + 2));
	Cap.resize(N + 2, vector<int>(N + 2));
	G.resize(N + 2);

	for(int i = 1 ; i <= N; i++)
		RF[i][i] = 0;

	for(int i = 0; i < M; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		outDeg[x] ++;
		inDeg[y] ++;
		RF[x][y] = c;
		MinCost += c;
	}

	fin.close();


	for(int k = 1; k <= N; k++)
	{
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= N; j++)
			{
				if(RF[i][k] + RF[k][j] < RF[i][j])
				{
					RF[i][j] = RF[i][k] + RF[k][j];
				}
			}
		}
	}

	for(int i = 1; i <= N; i++)
	{
		if(inDeg[i] > outDeg[i])
		{
			lefts.push_back(i);
		}
		else if(inDeg[i] < outDeg[i])
		{
			rights.push_back(i);
		}
	}

	for(vector<int>::iterator itr = lefts.begin();
		itr != lefts.end();
		itr++)
	{
		G[0].push_back(*itr);
		Cost[0][*itr] = 0;
		Cap[0][*itr] = inDeg[*itr] - outDeg[*itr];
	}

	for(vector<int>::iterator itr = rights.begin();
		itr != rights.end();
		itr++)
	{
		G[*itr].push_back(N + 1);
		Cost[*itr][N+1] = 0;
		Cap[*itr][N+1] = outDeg[*itr] - inDeg[*itr];
	}

	for(vector<int>::iterator itr = lefts.begin();
		itr != lefts.end();
		itr++)
	{
		for(vector<int>::iterator itr2 = rights.begin();
			itr2 != rights.end();
			itr2++)
		{
			G[*itr].push_back(*itr2);
			G[*itr2].push_back(*itr);

			Cap[*itr2][*itr] = 0;
			Cap[*itr][*itr2] = INF;

			Cost[*itr2][*itr] = -RF[*itr][*itr2];
			Cost[*itr][*itr2] = RF[*itr][*itr2];
		}
	}

	while(Bellman());


	fstream fout(outfile.c_str(), ios::out);
	fout << MinCost << "\n";
	fout.close();
}