#include <stdio.h>
#include <assert.h>
#include <string.h>

enum { maxnodes = 64 };

int nodes;
int dist[maxnodes][maxnodes];
int next[maxnodes][maxnodes]; //next node in path from i to j
int indeg[maxnodes],
    outdeg[maxnodes];
int morein[maxnodes], moreins,
    moreout[maxnodes], moreouts;
int ans;

void floyd_warshall()
{
	int i, j, k;

	for(k = 0; k < nodes; k++) //intermediate
		for(i = 0; i < nodes; i++)
			for(j = 0; j < nodes; j++)
				if(dist[i][j] > dist[i][k] + dist[k][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					next[i][j] = k;
				}

	for(i = 0; i < nodes; i++)
		for(j = 0; j < nodes; j++)
			printf("dist %d %d is %d\n", i, j, dist[i][j]);
	printf("\n");
}

void go()
{
	int i, ini, outi;

	for(i = 0; i < nodes; i++)
	{
		printf("node %d indeg %d outdeg %d\n", i, indeg[i], outdeg[i]);

		if(indeg[i] < outdeg[i])
			moreout[moreouts++] = i;
		else if(indeg[i] > outdeg[i])
			morein[moreins++] = i;
	}

	printf("%d moreouts, %d moreins\n", moreouts, moreins);

	for(ini = 0, outi = 0; ini < moreins && outi < moreouts; )
	{
		printf("ini %d outi %d linking %d w/ %d (cost %d)\n", ini, outi, morein[ini], moreout[outi],
				dist[ morein[ini] ][ moreout[outi] ]);

		ans += dist[ morein[ini] ][ moreout[outi] ];

		outdeg[ morein[ini] ]++;
		indeg[ moreout[outi] ]++;

		if(outdeg[ morein[ini] ] == indeg[ morein[ini ] ])
			ini++;

		if(outdeg[ moreout[outi] ] == indeg[ moreout[ outi ] ])
			outi++;
	}

	assert(ini == moreins);
	assert(outi == moreouts);

	printf("ans %d\n", ans);
}

int main()
{
	int i, a, b, cost, edges;
	FILE *f = fopen("traseu.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &nodes, &edges);

	memset(dist, 0x3F, sizeof(dist)); //inf
	for(i = 0; i < nodes; i++)
		dist[i][i] = 0;

	for(i = 0; i < edges; i++)
	{
		fscanf(f, "%d%d%d", &a, &b, &cost);
		a--; b--;

		dist[a][b] = cost;

		outdeg[a]++;
		indeg[b]++;

		ans += cost;
	}

	fclose(f);
	f = fopen("traseu.out", "w");
	if(!f) return 1;

	floyd_warshall();
	go();

	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}