#include<cstdio>
#include<vector>
#include<deque>
int n,m,x,y,max,min,dk[250001],viz[250001],nr[1001];
char s[100],*p;
std::vector<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){
		a[x].push_back(std::make_pair(y,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<a[i].size();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;
	for(int i=1;i<=m;i++)
		read();
	if(max==min) printf("%d\n",min);
	else
		printf("%d\n",dijkstra(min,max));
	fclose(stdout);
	return 0;
}