#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
int re[1001][1001];// 邻接矩阵  
int tt[10001];// 队列 数组 
bool in[1001];// 标记每个点是否已经在队里 
int d[1001];// 从start 到 每个点的最优距离数组  
/* 
 	我理解的SPFA就是每次通过队头的元素去松弛跟他有关系的点，并把这些点加入队尾。
	队头出队。
	这个过程一直持续到都不能在松弛为止。
	如果一个点从队列进进出出超过n次，那么这个图是有问题的，即有负环。  
	其间有个d数组记录距离。
	最后返回他就好了。 
*/
int n;
int spfa(int start,int finish)
{
    freopen("longest.in","r",stdin);
    freopen("longest.out","w",stdout);
	memset(in,0,sizeof(in));
	memset(d,-1,sizeof(d));
	int i,head,end;
	head=end=0;
	tt[head]=start;
	d[start]=0;
	while (head<=end)
	{
		int x=tt[head];
		for (i=1;i<=n;i++)// 松弛  // 
			if (re[x][i]>0&&re[x][i]+d[x]<d[i])
			{
				d[i]=re[x][i]+d[x];//更新最优解 
				if (!in[i])//入队 
				{
					end++;
					tt[end]=i;
					in[i]=1;
				}
			}
		in[x]=0;//队头出队  
		head++;
	}
	return d[finish];
}
int main()
{
	int m,i,x,y,z;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		re[x][y]=z;
		re[y][x]=z;
	}
	printf("%d\n",spfa(1,n));
	//system("pause");
	return 0;
}