#include<cstdio>
#include<vector>
#include<deque>
int n,m,x,y,max,min,dk[250001],nr[1001],gr[250001],lm[500001][3],num,index[250001];
char s[100],*p,viz[250001];
std::pair<int,int> *a[250001];
std::deque<int> l[1001];
#pragma region Read
inline void read1()
{
	gets(s);
	p=s;
	while(*p==' ') p++;
	n=0;
	while(*p>='0' && *p<='9') {
		n=n*10+*p-'0';
		p++;}
	while(*p==' ') p++;
	m=0;
	while(*p>='0' && *p<='9') {
		m=m*10+*p-'0';
		p++;}
	while(*p==' ') p++;
	x=0;
	while(*p>='0' && *p<='9') {
		x=x*10+*p-'0';
		p++;}
	while(*p==' ') p++;
	y=0;
	while(*p>='0' && *p<='9') {
		y=y*10+*p-'0';
		p++;}
}
inline void read()
{
	int x,y,c;
	gets(s);
	p=s;
	while(*p==' ') p++;
	x=0;
	while(*p>='0' && *p<='9'){
		x=x*10+*p-'0';
		p++;}
	while(*p==' ') p++;
	y=0;
	while(*p>='0' && *p<='9'){
		y=y*10+*p-'0';
		p++;}
	while(*p==' ') p++;
	c=0;
	while(*p>='0' && *p<='9'){
		c=c*10+*p-'0';
		p++;}
	if(x!=y){
		gr[x]++;
		lm[++num][0]=x;
		lm[num][1]=y;
		lm[num][2]=c;
		if(c>max)  max=c;
		if(c<min)  min=c;}
}
#pragma endregion
int M(int a,int b)
{
	if(a<b) return b;
	return a;
}
int dijkstra(int min,int max)
{
	if(x==y) return 0;
	int i,j,k;
	for(i=1;i<=n;i++)
		dk[i]=max;
	dk[x]=min;
	l[min].push_back(x);
	while(1)
	{
		j=min;
		do{
			for(;j<max;j++)
				if(l[j].size()>nr[j]) break;

			if(j==max) break;

			while(l[j].size()>nr[j] && viz[l[j][nr[j]]]) 
				nr[j]++;

		}while(l[j].size()==nr[j]);

		if(j>=dk[y]) break;
		i=l[j][nr[j]];
		nr[j]++;
		if(i==y) break;
		viz[i]=1;
		for(j=0;j<gr[i];j++)
			if(!viz[a[i][j].first]){
				k=M(dk[i],a[i][j].second);
				if(k<dk[a[i][j].first]){
					dk[a[i][j].first]=k;
					l[k].push_back(a[i][j].first);}
			}
	}
	return dk[y];

}

int main()
{
	freopen("pscnv.in","r",stdin);
	freopen("pscnv.out","w",stdout);
	read1();
	max=0;min=1001;
	int i;
	for(i=1;i<=m;i++)
		read();
	for(i=1;i<=n;i++)
		a[i]=new std::pair<int,int> [gr[i]];
	for(i=1;i<=num;i++)
		a[lm[i][0]][index[lm[i][0]]++]=std::make_pair<int,int>(lm[i][1],lm[i][2]);
	if(max==min) printf("%d\n",min);
	else
		printf("%d\n",dijkstra(min,max));
	fclose(stdout);
	return 0;
}