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

using namespace std;

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

const int INF = 0x3f3f3f3f;
const int N = 41+41;

int n, m;
int gin[N], gout[N];

//original graph
namespace og{
	int dist[N][N];
	
	void nuke(){
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				if(i != j){
					dist[i][j] = INF;
				}
			}
		}
	}
	
	void royfloy(){
		for(int a = 1; a <= n; ++a){
			for(int b = 1; b <= n; ++b){
				for(int i = 1; i <= n; ++i){
					dist[a][b] = min(dist[a][b], dist[a][i]+dist[i][b]);
				}
			}
		}
	}
}

int s, d;
void setup(){
	s = 0;
	d = n+1;
	og::nuke();
}

int ans = 0;
void read(){
	fin >> n >> m;
	setup();
	for(int i = 0; i < m; ++i){
		int a, b;
		fin >> a >> b >> og::dist[a][b];
		ans += og::dist[a][b];
		gout[a]++;gin[b]++;
	}
}

//bipartite graph
namespace bp{
	int cap[N][N], flo[N][N];
	int cst[N][N];
	vector<int> gra[N];
	
	void biparthick(){
		for(int a = 1; a <= n; ++a){
			int da = gin[a]-gout[a];
			if(da > 0){
				cap[s][a] = da;
				gra[s].push_back(a);
			}else if(da < 0){
				cap[a][d] = -da;
				gra[a].push_back(d);
			}
			
			for(int b = 1; b <= n; ++b){
				int db = gin[b]-gout[b];
				if(da > 0 && db < 0){
					cst[a][b] = og::dist[a][b];
					cst[b][a] = -cst[a][b];
					
					gra[a].push_back(b);
					gra[b].push_back(a);
					
					cap[a][b] = INF;
				}
			}
		}
	}
	
	queue<int> q;
	bool inq[N];
	int dist[N], dad[N];
	void bellnuke(){
		for(int a = s; a <= d; ++a){
			dist[a] = INF;
		}
	}
	
	bool bellman(){
		bellnuke();
		q.push(s);
		dist[s] = 0;
		while(!q.empty()){
			int a = q.front();q.pop();
			inq[a] = false;
			for(auto b : gra[a]){
				int v = dist[a]+cst[a][b];
				if(v < dist[b] && flo[a][b] < cap[a][b]){
					dist[b] = v;
					dad[b] = a;
					if(!inq[b]){
						q.push(b);
						inq[b] = true;
					}
				}
			}
		}
		return dist[d] != INF;
	}
	
	void maxflow(){
		int fmin = INF;
		for(int x = d; x != s; x = dad[x]){
			fmin = min(fmin, cap[dad[x]][x] - flo[dad[x]][x]);
		}
		for(int x = d; x != s; x = dad[x]){
			flo[dad[x]][x] += fmin;
			flo[x][dad[x]] -= fmin;
		}
		ans += dist[d]*fmin;
	}

	void flowerize(){
		while(bellman()){
			maxflow();
		}
	}
}

void solve(){
	og::royfloy();
	bp::biparthick();
	bp::flowerize();
}

int main(){
	// ios_base::sync_with_stdio(false);
	read();
	solve();
	fout << ans;
	return 0;
}