//#include "stdafx.h"
#include <iostream>
#include <map>

using namespace std;

map<int, map<int, int> > Map;
int N, M, a, b, c;
const int INIT = 1000000000;

int Dijkstra()
{
	int minnum, v, i, j;
	bool *B = new bool[N+1];
	int *D = new int[N+1];
	for(i = 1; i <= N; i++) B[i] = false;
	B[1] = true, D[1] = 0;
	for(i = 2; i <= N; i++)
	{
		if(Map[1][i]) D[i] = Map[1][i];
		else D[i] = INIT;
	}
	for(i = 2; i <= N; i++)
	{
		minnum = INIT;
		for(j = 2; j <= N; j++)
		{
			if(!B[j] && minnum > D[j])
			{
				v = j;
				minnum = D[j];
			}
		}
		if(v == N) return D[N];
		B[v] = true;
		for(j = 1; j <= N; j++)
		{
			if(!B[j] && Map[v][j])
			{
				if(minnum + Map[v][j] < D[j])
					D[j] = Map[v][j] + minnum;
			}
		}
	}
	return D[N];
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		Map[a][b] = c;
	}
	int num = Dijkstra();
	printf("%d\n",num);
	//system("pause");
	return 0;
}