// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.138876710346101x):
#include<bits/stdc++.h>

using namespace std;



const int N = 1e5 + 10, M = 2e5 + 30;

int n, m;

struct edge {

    int y, nxt, id;

}e[M << 1];

int lin[M], len;

int dis[N], pos[N];

bool vis[N];

set<int> c[N];



inline int read() {

    int s = 0, f = 1;

    char ch;

    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-')   f = -1;

    for(; ch >= '0' && ch <= '9'; ch = getchar())   s = (s << 1) + (s << 3) + ch - '0';

    return s * f;

}



inline void add(int xx, int yy, int vv) {

    e[++len] = (edge){yy, lin[xx], vv};

    lin[xx] = len;

}



inline void Dijkstra() {

    priority_queue< pair < int, int > > q;

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

    memset(vis, 0, sizeof(vis));

    dis[1] = 0;

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

    while(!q.empty()) {

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

        if(vis[x])  continue;

        vis[x] = 1;

        for(int i = lin[x]; i; i = e[i].nxt) {

            int y = e[i].y, v = c[x].count(e[i].id) ? 0 : 1;

            if(dis[y] > dis[x] + v) {

                dis[y] = dis[x] + v;

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

                c[y].clear();

                c[y].insert(e[i].id);

            } else if(dis[y] == dis[x] + v) c[y].insert(e[i].id);

        }

    }

}



int main() {

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

    if(m == 0) { puts("-1"); return 0; }

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

        int xx = read(), yy = read(), vv = read();

        add(xx, yy, vv);

        add(yy, xx, vv);

    }

    Dijkstra();

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

    return 0;

}