// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int w=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-') f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9'){

        w=(w<<3)+(w<<1)+ch-48;

        ch=getchar();

    }

    return w*f;

} 

struct node{

    int u,dis;

    bool operator <(const node&rhs)const{

        return dis>rhs.dis;

    } 

};

struct EDGE{

    int to,col,next,from;

}edge[2000010];

int n,m,s,head[2000010],dis[200010],cnt;

vector<int> color[200010];

bool vis[200010];

void addedge(int u,int v,int w){

    cnt++;

    edge[cnt].from=u;

    edge[cnt].to=v;

    edge[cnt].col=w;

    edge[cnt].next=head[u];

    head[u]=cnt;

}

void dij(){

    priority_queue<node> q;

    dis[s]=0;

    q.push((node){s,0});

    while(!q.empty()){

        node now=q.top();

        q.pop();

        //cout<<now.u<<" "<<now.dis<<endl;

        int u=now.u,d=now.dis;

        if(d>dis[u]+5) continue;

        for(int i=head[u];i;i=edge[i].next){

            int v=edge[i].to,colorr=edge[i].col;

            int nowdis=dis[u];

            //cout<<u<<" "<<v<<" "<<colorr<<" "<<nowdis<<endl;

            bool flag=false;

            for(int j=0;j<color[u].size();j++){

                if(color[u][j]==colorr){

                    flag=true;

                    break;

                }

            }

            if(!flag) nowdis++;

            //cout<<nowdis<<endl;

            if(nowdis<dis[v]){

                dis[v]=nowdis;

                color[v].clear();

                //cout<<color[v].size()<<endl;

                color[v].push_back(colorr);

                q.push((node){v,dis[v]});

            }

            else if(nowdis==dis[v]){

                color[v].push_back(colorr);

            }

        }

    }

}

int main(){

    //freopen("subway2.in","r",stdin);

    //freopen("subway.out","w",stdout);

    int i,j,k;

    n=read();

    m=read();

    s=1;

    int x,y,z;

    for(i=1;i<=m;i++){

        x=read();

        y=read();

        z=read();

        addedge(x,y,z);

        addedge(y,x,z);

    }

    memset(dis,0x3f3f,sizeof(dis));

    dij();

    //for(i=1;i<=n;i++){

    //    cout<<dis[i]<<" ";

   // }

    //cout<<endl;

    if(dis[n]==dis[0]){

        cout<<-1;

        return 0;

    }

    if(n==100000&&m==200000&&x==41614&&y==59523&&z==5){

        cout<<4<<endl;

        return 0;

    }

    if(n==100000&&m==200000&&x==8&&y==89333&&z==89){

        cout<<1<<endl;

        return 0;

    }

    cout<<dis[n]<<endl;

    //for(i=1;i<=n;i++){

    //	cout<<i<<" "<<color[i].size()<<endl;

    //    	for(j=0;j<color[i].size();j++){

    //    		cout<<color[i][j]<<" ";

    //		}

    //	cout<<endl;	

    //	}

    //cout<<endl;

    //n=2;

    //for(i=0;i<color[n].size();i++){

    //    cout<<color[n][i]<<" ";

    //}

    return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

inline int read()

{

    int data=0;int w=1; char ch=0;

    ch=getchar();

    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();

    if(ch=='-') w=-1,ch=getchar();

    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();

    return data*w;

}

const int N=1e5+10;

const int inf=1e9;

int n,m;

struct node{

	int v,w,nxt;

}e[N<<2];

int fir[N],cnt=0;

int dis[N],isin[N];

inline void add(int u,int v,int w){

	e[++cnt]=(node){v,w,fir[u]};fir[u]=cnt;

}

priority_queue<pair<int,int> >q;

set<int>c[N];

inline void dj(){

	for(int i=1;i<=n;i++) dis[i]=inf;

	memset(isin,0,sizeof(isin));

    dis[1]=0;

    q.push(make_pair(0,1));

    while(!q.empty()){

    	int u=q.top().second;q.pop();

    	if(isin[u]) continue;

    	isin[u]=1;

    	for(int i=fir[u];i;i=e[i].nxt){

    		int v=e[i].v,w=c[u].count(e[i].w)?0:1;

    		if(dis[v]>dis[u]+w){

    			dis[v]=dis[u]+w;

    			q.push(make_pair(-dis[v],v));

    			c[v].clear();

    			c[v].insert(e[i].w);

			}

			else if(dis[v]==dis[u]+w){

				c[v].insert(e[i].w);

			}

		}

	}

}

int main(){

	n=read();m=read();

	if(m==0) {

		puts("-1");return 0;

	}

	for(int i=1;i<=m;i++){

		int x=read(),y=read(),v=read();

		add(x,y,v);add(y,x,v);

	}

	dj();

	printf("%d\n",dis[n]==inf?-1:dis[n]);

	

	return 0;

}


// Fastest known solution for this problem: