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

#define min(a,b) (a < b ? a : b)

int N, M;
int x, y, z;
int V1, V2;

int main()
{
	freopen("maxflow.in", "r", stdin);
	freopen("maxflow.out", "w", stdout);

	int x, y, z, i;

	scanf("%d %d ", &N, &M);

	assert(1 <= N && N <= 1000);
	assert(1 <= M && M <= 5000);

	for (i = 1; i <= M; i++)
	{
		scanf("%d %d %d ", &x, &y, &z);

		assert(1 <= x && x <= N);
		assert(1 <= y && y <= N);
		assert(1 <= z <= 110000);

		assert(x != N);
		assert(y != 1);

		if (x == 1) V1 += z;
		if (y == N) V2 += z;
	}

	printf("%d\n", min(V1, V2));

	return 0;
}