#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN=2005;
const int MAXM=30005;
const int inf=100000000;

struct node
{
	int u, v, f;
	int c;
	int next;
};

int dis[MAXN];
int pre[MAXN];
int head[MAXN];
bool vis[MAXN];
node e[MAXM];
int N, M, cnt;
int S, T;

void addedge(int u, int v, int f, int c)
{
	e[cnt].u=u; e[cnt].v=v; e[cnt].c=c; e[cnt].f=f; e[cnt].next=head[u]; head[u]=cnt++;
	e[cnt].u=v; e[cnt].v=u; e[cnt].c=-c; e[cnt].f=0; e[cnt].next=head[v]; head[v]=cnt++;
}

bool spfa()
{
	queue<int> q;
	while (!q.empty()) q.pop();
	for (int i=0; i<=2*N; i++)
	{
		dis[i]=inf, vis[i]=0;
		pre[i]=-1;
	}
	q.push(S); vis[S]=1; dis[S]=0;
	while (!q.empty())
	{
		int u=q.front(); q.pop();
		for (int now=head[u]; now!=-1; now=e[now].next)
		{
			int v=e[now].v;
			if (e[now].f>0&&dis[v]>dis[u]+e[now].c)
			{
				dis[v]=dis[u]+e[now].c;
				pre[v]=now;
				if (!vis[v])
				{
					q.push(v);
					vis[v]=true;
				}
			}
		}
		vis[u]=false;
	}
	return (dis[T]<inf);
}

int MCMF()
{
	int mincost=0;
	while (spfa())
	{
		int nec=inf;
		for (int now=pre[T]; now!=-1; now=pre[e[now].u])
			nec=min(nec, e[now].f);
		mincost+=nec*dis[T];
		for (int now=pre[T]; now!=-1; now=pre[e[now].u])
		{
			e[now].f-=nec;
			e[now^1].f+=nec;
		}
	}
	return mincost;
}

int main()
{
	while (scanf("%d%d", &N, &M)==2)
	{
		S=1; T=N*2; cnt=0;
		memset(head, -1, sizeof(head));
		addedge(1, 1+N, 2, 0);
		addedge(N, N+N, 2, 0);
		for (int i=2; i<N; i++) addedge(i, i+N, 1, 0);
		while (M--)
		{
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			addedge(u+N, v, 1, w);
		}
		printf("%d\n", MCMF());
	}
	return 0;
}
