//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define swap(p,q) r=(p);(p)=(q);(q)=r
#define INF 1000000000000//10^12
#define INFINT 2000000001//2*10^9+1
#define MOD 1000000007

using namespace std;

struct kari_edge{
	int to;
	int rosen;
};

struct edge{
	int to;
	int cost;
};

int compare_rosen(const void *a, const void *b) {
	struct kari_edge *A = (struct kari_edge *)a;
	struct kari_edge *B = (struct kari_edge *)b;
	return A->rosen - B->rosen;
}

typedef pair<int, int> P;

int V;//辺の本数
static vector<edge> G[1000010];//辺の情報　手で埋めておく必要あり
static int d[1000010];

void init(int dd[], int num){
	int i;
	for(i=0;i<num;i++){
		dd[i]=INFINT;
	}
}

void dijkstra(int s){

	priority_queue<P, vector<P>, greater<P> > que;
	init(d,1000010);
	d[s]=0;
	que.push(P(0,s));

	while(!que.empty()){
		P p=que.top();
		que.pop();
		int v=p.second;
		if(d[v]<p.first) continue;
		for(int i=0; i<G[v].size(); i++){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

//void型なので返り値は無し　d[]に結果が格納されるので欲しいものをansに
int main(void)
{
	//変数の宣言
	int n,m;
	static int p[200010];
	static int q[200010];
	static int c[200010];
	struct kari_edge ke;
	static vector<kari_edge> map[100010];
	static vector<int> point[1000010];
	struct edge e;
	static struct kari_edge temparray[100010];
	static kari_edge pointinv[1000010];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	int temp,temp1,temp2;
	int max,min;
	int len;
	int sum=0;
	int ok,ng;



	//データの読み込み


	scanf("%d %d",&n,&m);
//	scanf_s("%d %d",&n,&m);


	for(i=0;i<m;i++){
		scanf("%d %d %d",&p[i],&q[i],&c[i]);
//		scanf_s("%d %d %d",&p[i],&q[i],&c[i]);
		ke.to=q[i];
		ke.rosen=c[i];
		map[p[i]].push_back(ke);
		ke.to=p[i];
		map[q[i]].push_back(ke);
	}

	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

	for(i=1;i<=n;i++){
		for(j=0;j<map[i].size();j++){
			temparray[j]=map[i][j];
		}

		qsort(temparray,map[i].size(),sizeof(kari_edge),compare_rosen);

		for(j=0;j<map[i].size();j++){
			map[i][j]=temparray[j];
		}
	}

	temp=0;
	for(i=1;i<=n;i++){
		point[i].push_back(temp);
		pointinv[temp].to=i;
		pointinv[temp].rosen=0;
		temp++;
		for(j=0;j<map[i].size();j++){
			if(j==0||map[i][j].rosen!=map[i][j-1].rosen){
				point[i].push_back(temp);
				pointinv[temp].to=i;
				pointinv[temp].rosen=map[i][j].rosen;
				temp++;
			}
		}
	}

	for(i=1;i<=n;i++){
		for(j=1;j<point[i].size();j++){
			e.to=point[i][j];
			e.cost=1;
			G[point[i][0]].push_back(e);
			e.to=point[i][0];
			e.cost=0;
			G[point[i][j]].push_back(e);
		}
	}

	for(i=0;i<m;i++){
		ok=-1;
		ng=temp;
		while(ng-ok>1){
			if(pointinv[(ok+ng)/2].to>p[i]||(pointinv[(ok+ng)/2].to==p[i]&&pointinv[(ok+ng)/2].rosen>c[i])){
				ng=(ok+ng)/2;
			}else if(pointinv[(ok+ng)/2].to<p[i]||(pointinv[(ok+ng)/2].to==p[i]&&pointinv[(ok+ng)/2].rosen<c[i])){
				ok=(ok+ng)/2;
			}else{
				temp1=(ok+ng)/2;
				break;
			}
		}

		ok=-1;
		ng=temp;
		while(ng-ok>1){
			if(pointinv[(ok+ng)/2].to>q[i]||(pointinv[(ok+ng)/2].to==q[i]&&pointinv[(ok+ng)/2].rosen>c[i])){
				ng=(ok+ng)/2;
			}else if(pointinv[(ok+ng)/2].to<q[i]||(pointinv[(ok+ng)/2].to==q[i]&&pointinv[(ok+ng)/2].rosen<c[i])){
				ok=(ok+ng)/2;
			}else{
				temp2=(ok+ng)/2;
				break;
			}
		}

		e.to=temp1;
		e.cost=0;
		G[temp2].push_back(e);
		e.to=temp2;
		G[temp1].push_back(e);

		}

	dijkstra(0);

	//	printf("計算部分終了\n");

	//出力
	ans=INFINT;
	temp--;
	while(pointinv[temp].to==n){
		ans=min(ans,d[temp]);
		temp--;
	}

	if(ans==INFINT) ans=-1;

	printf("%d",ans);

	//	printf("結果の出力終了\n");


	return 0;
}



Measured memory_bytes: 92896