#include <stdio.h>

struct nod
{
	int nr,c;
	nod *adr;
} *graf[65],*u;
struct elem
{
	int nr;
	elem *adr;
} *c,*sf,*u2;
int n,m,i,x,y,z,d[111700],s[111700],j,a[65][65],viz[111700][59],node,lim;

inline bool e(int nod_comp,int muchie)
{
	if (muchie%32)
		return viz[nod_comp][muchie/32] & (1<<(muchie%32-1));
	return (viz[nod_comp][muchie/32-1]>>1) & (1<<30);
}

inline void add(int nod_comp,int muchie)
{
	if (muchie%32)
		viz[nod_comp][muchie/32]|=(1<<(muchie%32-1));
	else
	{
		int bit0=viz[nod_comp][muchie/32-1] & 1;
		viz[nod_comp][muchie/32-1]=((viz[nod_comp][muchie/32-1]>>1)|(1<<30))<<1+bit0;
	}
}

int main()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&z);
		u=new nod;
		u->nr=y;
		u->c=z;
		u->adr=graf[x];
		graf[x]=u;
		a[x][y]=i;
	}
	c=new elem;
	c->nr=m+1;
	c->adr=NULL;
	sf=c;
	for (i=1;i<=n;++i)
		for (j=0;j<=m;++j)
		{
			d[i*(m+1)+j]=2147000000;
			s[i*(m+1)+j]=0;
		}
	s[m+1]=1;
	d[m+1]=0;
	while (c)
	{
		for (u=graf[c->nr/(m+1)];u;u=u->adr)
		{
			if (e(c->nr,a[c->nr/(m+1)][u->nr]))
				x=c->nr%(m+1);
			else
				x=c->nr%(m+1)+1;
			node=u->nr*(m+1)+x;
			if (d[c->nr]+u->c<d[node])
			{
				d[node]=d[c->nr]+u->c;
				lim=m/32+1;
				for (j=0;j<=lim;++j)
					viz[node][j]=viz[c->nr][j];
				add(node,a[c->nr/(m+1)][u->nr]);
				if (!s[node])
				{
					s[node]=1;
					u2=new elem;
					u2->nr=node;
					u2->adr=NULL;
					sf->adr=u2;
					sf=u2;
				}
			}
		}
		s[c->nr]=0;
		u2=c;
		c=c->adr;
		delete u2;
	}
	printf("%d",d[2*m+1]);
	return 0;
}