#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#define N 100010
using namespace std;
ifstream in("regexp.in");
ofstream out("regexp.out");
int n,m;
int INF=(1<<28);
vector<int> F[N],B[N],G[N],C[N];
bool l[N]={0};
vector<int> scc[N];
int dfn[N]={0},low[N]={0};
int color[N]={0};
int col=0,tim=0;
int f[N]={0};
stack<int> S;
void tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	l[u]=1;
	S.push(u);
	int i,v;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!dfn[v])
		{
			//out<<u<<' '<<v<<endl;
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(l[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		col++;
		do
		{
			v=S.top();
			l[v]=0;
			scc[col].push_back(v);
			color[v]=col;
			S.pop();
		}while(u!=v);
	}
}
void Dijkstra(int s)
{
	priority_queue <pair<int,int> > q;
	int i,u,v,w;
	memset(l,0,sizeof(l));
	for(i=1;i<=n;i++)f[i]=INF;
	f[s]=0;
	q.push(make_pair(-f[s],s));
	while(!q.empty())
	{
		u=q.top().second;
		q.pop();
		l[u]=0;
		for(i=0;i<F[u].size();i++)
		{
			v=F[u][i];
			w=B[u][i];
			if(f[v]>f[u]+w)
			{
				f[v]=f[u]+w;
				if(!l[v])
				{
					l[v]=1;
					q.push(make_pair(-f[v],v));
				}
			}
		}
	}
}
void SCC()
{
	int i;
	for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	/*for(i=1;i<=n;i++)out<<color[i]<<' ';
	out<<endl;*/
}
void rebuild()
{
	int i,j,u,v;
	//map<int,pair<int,int> > F;
	for(i=1;i<=n;i++)
	{
		u=color[i];
		for(j=0;j<G[i].size();j++)
		{
			v=color[G[i][j]];
			//out<<u<<' '<<v<<' '<<C[i][j]<<' '<<endl;
			F[u].push_back(v);
			B[u].push_back(C[i][j]);
		}
	}
}
void read()
{
	int i,u,v,w;
	in>>n>>m;
	for(i=1;i<=n;i++)
	{
		in>>u>>v>>w;
		G[u].push_back(v);
		//out<<u<<' '<<v<<endl;
		C[u].push_back(w);
	}
}
void print()
{
	int i,j;
	for(i=1;i<=col;i++)
	{
		for(j=0;j<F[i].size();j++)
		{
			//out<<i<<' '<<F[i][j]<<' '<<B[i][j]<<endl;
		}
	}
}
void work()
{
	SCC();
	rebuild();
	//print();
	Dijkstra(color[1]);
	out<<f[color[n]]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}