#include <bits/stdc++.h>
        #include<iostream>
        #include<cstdio>
        #include<vector>
        #include<queue>
        #include<map>
        #include<cstring>
        #include<string>
        #include <math.h>
        #include<algorithm>
    //    #include <boost/multiprecision/cpp_int.hpp>
        #include<functional>
  //    #define int long long
        #define inf  1000000007
        #define pa pair<int,int>
#define ll long long
        #define pal pair<ll,ll>
        #define ppa pair<int,pa>
        #define  mp make_pair
        #define EPS (1e-10)
        #define equals(a,b) (fabs((a)-(b))<EPS)

        using namespace std;

        class Point{
        	public:
        	double x,y;
        	Point(double x=0,double y=0):x(x),y(y) {}
        	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
        	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
        	Point operator * (double a) {return Point(x*a,y*a);}
        	Point operator / (double a) {return Point(x/a,y/a);}
        	double absv() {return sqrt(norm());}
        	double norm() {return x*x+y*y;}
        	bool operator < (const Point &p) const{
        		return x != p.x ? x<p.x: y<p.y;
        	}
        	bool operator == (const Point &p) const{
        		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
        	}
        };
        typedef Point Vector;

        struct Segment{
        Point p1,p2;
        };

    double hen(Vector a){
    if(fabs(a.x)<EPS && a.y>0) return acos(0);
    else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
    else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
    else if(fabs(a.y)<EPS && a.x>0) return 0.0;
    else if(a.y>0) return acos(a.x/a.absv());
    else return 2*acos(0)+acos(-a.x/a.absv());

    }

        double dot(Vector a,Vector b){
        	return a.x*b.x+a.y*b.y;
        }
        double cross(Vector a,Vector b){
        	return a.x*b.y-a.y*b.x;
        }
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        //----------------kokomade temple------------

int n,m;
set<int> nori[100003];
set<int> vis[100003]; 
vector<pa> G[100003];
priority_queue<ppa,vector<ppa>, greater<ppa> > pq;

signed main(){
cin>>n>>m;
	for(int i=0;i<m;i++){
		int pp,qq,cc;
		cin>>pp>>qq>>cc;
		nori[qq].insert(cc);
		nori[pp].insert(cc);
		G[pp].push_back(mp(cc,qq));
		G[qq].push_back(mp(cc,pp));
	}
	
	for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
	
	pq.push(mp(0,mp(1,0)));
	
	while(pq.size()>0){
		ppa zz=pq.top();
		pa z=zz.second;
		pq.pop();
		if(z==mp(n,0)){
			cout<<zz.first<<endl;
			return 0;
		}
		if(vis[z.first].find(z.second)!=vis[z.first].end()) continue;
		vis[z.first].insert(z.second);
		if(z.second==0){
			for(auto x : nori[z.first]) {
				if(vis[z.first].find(x)!=vis[z.first].end()) continue;
				pq.push(mp(1+zz.first,mp(z.first,x)));
    		}
		}
		else{
			if(vis[z.first].find(0)==vis[z.first].end()){
				pq.push(mp(zz.first,mp(z.first,0)));
			}
			int s=upper_bound(G[z.first].begin(),G[z.first].end(),mp(z.second,-1))-G[z.first].begin();
			int t=upper_bound(G[z.first].begin(),G[z.first].end(),mp(1+z.second,-1))-G[z.first].begin();
			t--;
			for(int i=s;i<=t;i++){
				if(vis[G[z.first][i].second].find(G[z.first][i].first)!=vis[G[z.first][i].second].end()) continue;
				pq.push(mp(zz.first,mp(G[z.first][i].second,z.second)));
			}
		}
		
	}
	cout<<"-1"<<endl;
	return 0;
        }
        
//printf("%.10f\n",ans);


Measured memory_bytes: 56756