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

#include <string.h>

#include <set>

#include <queue>

#define N 100010

using namespace std;

int n,m,d[N];

int ne=0,h[N];struct edge{int to,w,x;}e[400010];

inline void ins(int s,int t,int w) {

	e[++ne].to=t;e[ne].w=w;e[ne].x=h[s];h[s]=ne;

}

struct stat {

	int n,d;

	stat(){}

	stat(int a,int b){n=a;d=b;}

	inline bool operator>(const stat& a) const {

		return d!=a.d?d>a.d:n<a.n;

	}

};

set<int> vis[N];

inline int dij(int s,int t) {

	priority_queue<stat,vector<stat>,greater<stat> > q;

	stat u;int v,oo,nd;

	memset(d,33,sizeof(d));oo=*d;

	d[s]=0;q.push(stat(s,0));

	while(!q.empty()) {

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

		if(u.d>d[u.n]) continue;

		for(int i=h[u.n];i;i=e[i].x) {

			v=e[i].to;nd=u.d+(vis[u.n].count(e[i].w)?0:1);

			if(nd<d[v]) {

				d[v]=nd;q.push(stat(v,nd));

				vis[v].clear();

			}

			if(nd==d[v]) vis[v].insert(e[i].w);

		}

	}

	return oo==d[t]?-1:d[t];

}

int main() {

	int a,b,c;

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

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

		scanf("%d%d%d",&a,&b,&c);

		ins(a,b,c);ins(b,a,c);

	}

	printf("%d",dij(1,n));

	return 0;

}

// Optimized solution to the same problem (faster):
/*

 *                             UM.

 *                            J@B@1                                                                    iO@1

 *                           Y@@@B@BB.                                                              7B@B@B@

 *                          :@B@i,B@B@O                                                          ,Z@B@B@B@Br

 *                          @B@q   i@B@BS                                                      7@B@@@O5vMB@q

 *                         8@@B      LB@B@i                                                  FB@@@BNjYjLE@B@

 *                        ,B@B:        0@@@Z                                               P@B@BM1JJ125JPB@B

 *                        B@BB          :@B@B                                            XB@B@Z2LuU52F2u2@B@.

 *                       :@B@             @@@B:                                        v@B@B8uJj51F1525uUB@B7

 *                       @B@O              0@@B.               ..::ir7vvYUuU777r::.   B@B@OULU2F2F151F11Y@B@S

 *                       B@B,               8B@B  :ruXMB@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@5Jj1211F1F1F2FUJO@BB

 *                      U@B@                 @B@B@B@B@B@@@B@B@B@MMqPS5JuYL7rq@B@OBB@B@B8Yu211F1515251515YGB@@

 *                      @B@u                 v@@@@MSur:.                    LB@MvvjJuU5YU252F1F1F25251F2uX@@@

 *                      @@@.                                                N@BML2U2UUU12F15252525251515Jk@@B

 *                     r@B@                                                 YB@Bju52121252515252F15251F2u5@B@

 *                     PB@B                                                  @@@PYUF151F25151F152F2F1F15jF@@B

 *                     @@BS                                                  N@@@UJ2F25252F251525151F1F1u5@B@

 *                     @@@7                                                   B@B@5Yj12F152F1F1F25252515jFB@B

 *                     B@Bi                                                    M@B@O2Luu52525212F151121UY1@B@7

 *                    O@B@:                                                     v@B@BMSuYJJuuUu2u2uujjYJJXB@B@M

 *                  7B@B@,                                                        1B@@@B@GPF1uujuu21PNMB@B@B@B@@

 *                 qB@B2                                                            i8B@B@B@B@B@@@@@B@B@B@q: @@@B

 *                MB@B:                                                                 7SBB@B@B@B@B@Zu:      @B@B

 *               ZB@B.                                              ,v.                                        @B@L

 *              LB@B,                         Y7                    @B@Bu                                      7@B@

 *   :B@B@@B2:  @@B7                         @B@Z                   r@B@B@BP:                                   B@BE

 *    BB@@@B@B@B@BE                        r@B@B                       7@B@B@B@Ou:                              iB@B

 *         :uM@@B@@2.           :7::::ivk@B@B@0                           :5B@B@B@B@B@B@G.                       @B@i

 *            BB@@@B@@         :@B@B@@@B@B@@1                                 .i5M@B@B@@@5                       M@@2

 *            B@B ,@B1          L0EZZG0F7:                                            .:,                        uB@MrP@M7

 *           2@B@                                                                                               ,O@B@B@B@B

 *           @B@1                                                     :@B@@@r                                :@@@@B@BL:,,

 *           B@Bi                         :2ZS;                      :@B@B@B@r                               L@B@B@BU

 *           @B@.                        @@@B@B@                     vB@B@B@B5                                   @B@i

 *           B@B                        7B@B@B@BM                     OB@B@B@                                   ,B@B

 *           @B@                         @B@B@@@i                       rL7.                                    B@BM

 *           B@B7.:                       NB@@M.                                                               .@B@.

 *  .;JEB@@@B@B@B@B@.                                                                                       .  @B@u

 *@@@B@B@B@B@@@B@18U                                                                                      :B@B@B@BU,

 *7@BOui.    ,@@B                                                                                          SP@B@B@B@B@Or

 *            @@@U                                                                                           B@BJ.YO@B@B@i

 *            r@B@                                                                                         :B@Bk     .k@B@

 *             B@B@                                                                                       LB@@k         2i

 *              B@BM                                      .7jXEGqF7:                                     OB@@L

 *              .B@BM                                   .B@B@B@B@B@B@.                                 :@B@B:

 *               .B@B@                                   @@MYr::ivG@B                                .M@B@G

 *                 B@@@S                                                                           ,MB@B@,

 *                  v@@@BF                                                                      .1B@B@Br

 *                    2@@B@BL                                                                ,FB@@@B8,

 *                      r@B@B@BF,                                                        :YBB@B@B@B

 *                         L@B@B@B@P7,                                           .ivXB@B@B@B@B@M@B@

 *                            ,1B@B@B@B@@@BOP2L7i:,.              ..,:i7LSNB@@B@B@@@B@B@B@Z5v;.LB@@

 *                              @B@OEB@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@BM0SJ7i::::i:,u@B@

 *                              B@Bu ::i;7vu2XNGOMB@B@BMB@B@B@B@B@B@@@B1UFuj77ii:::::::iir;r;i.YB@B

 *                              @B@L.:i:i:i::::::::::..Y@B@BMYi:i;SB@B@N:.::i:iirir;r;rii::::ivO@B@

 *                              B@@X::,::::iirir;riri:E@B@1         ,@B@Br:;;r;rii:i::::i7JEB@@@@@B

 *                              @@@B@BBq5v7ii:::::::.2@@@i  ..,..     @B@@,,:::::irv2XMB@B@B@B@2@B@:

 *                             .B@BBB@@@B@B@B@BMNP5u7@B@1 .,,:,,  :.   @B@P50MB@B@B@B@B@@@BS:   @@B1

 *                             E@B@   ijGB@B@B@B@B@B@B@Bi .,:,,..@@B@7 B@B@B@B@B@B@BM57.        kB@B

 *                            .@B@:          .,ivu5Nq@B@u  ..,.. SB@B@@@B@PL7i,                 ,@B@

 *                            @@@8                   i@B@:    .     :B@B@@                       B@@2

 *                          i@@@@                     0@B@u          B@@B.                       vB@B

 *                         ,@B@G                       L@B@BOv:.:iFB@B@M                          @B@Bi

 *                          vNi                          S@@B@B@B@B@BM:                            MB@N

 *                                                          758BMqJ,

 *

 *                 .  YO.               vq                            :G       Z:

 *        SqOMBB@B@Br @@r rBE           @B     B@@@@@B@ONX8k    i::::.OB1.:::.u@O.::::i           @B@B@U:@@B@@BPEBu

 *        B@@NB@k.    5@i  uB@E.        BM     1U2uUJvirB@@Z   r@@B@B@@@B@B@B@B@B@@@B@Bi   LB@B@1 BX :@k uLLLvr@BJ:

 *            iB      iBi    7@     .@M8@BGMZZ         @@F            ,B       Pi          v@  Bq @i v@        B@

 *       vuL7r8@S7vJL7N@Z7LLri;72.   F7@Bvvv@@       @BX         @@@B@B@@@@@B@@@B@B@B      7@  @F Bi @q  @B@Bu @B

 *       N@B@G@@@8@BBOMB@G@BMNXG@,     B@   @@      .Bk          .:u;    i@:      Zv       7@  Bk @,;@  ,BY @B B@

 *            r@       @G     5.      ,@v   BZ :::,.r@E .::i,      @B     B@    .@BL       7@  @F B:i@. .@  @M @B

 *            7B: ,vO, @@   iB@:      @B   7@:MB@B@B@@@B@B@BM       @@.    B:  2@q         7@  BS @i 0@  B. @O B@

 *       ,r2EBB@B@B@Bi G@  @BB        B@   @B        @S              :    r@   ..          7B  @F @7  B7 @  @B @B

 *       E@B@UOBr       @B@Bi          L@0PB        .BZ        .@B@B@B@B@B@B@B@B@B@B@B@,   r@  BF @i  @G B@B@B B@

 *            7@,      kB@U    ;r        @@@.       .@Z                GBuL@iBBi           vB@B@q BP:5@7 @u,.  @B

 *            LBi   YB@BrB@    @@       @B:L@Br      BM             .M@B  rB  rB@J         v@. Pi @XZ8r  .     B@

 *        .   G@i B@BM.  ,B@,  @B    iB@B    N, 7r..q@k         ,LB@B8    J@,   i@B@B1r           Br           @@

 *        MB@B@B  ,i       B@B@B,    B@:        @B@B@F         .@BB:      P@i      :OBZ          .@U       B@B@B:

 *                          .ll                                           rB.                     :

 */

/*****************

 *   I<3   C++   *

 *  IWANT ANYAC  *

 * ILOVEPROGRAM! *

 *IT'SINTERESTING*

 * ILOVEPROGRAM! *

 *  INCONTESTS   *

 *   GETSCORE    *

 *    ACCODE     *

 *     LETS      *

 *      GO       *

 *Written by:    *

 *    charlieyan *

 *****************/

#include <assert.h>

#include <ctype.h>

#include <errno.h>

#include <float.h>

#include <fstream>

#include <iomanip>

#include <iostream>

#include <limits>

#include <locale>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#include <wchar.h>

#include <wctype.h>

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <numeric>

#include <list>

#define LL long long

#define pb push_back

#define pob pop_back

#define mp make_pair

#define FILL(a,v) memset((void*)a,v,sizeof(a))

#define FILL0(a) FILL(a,0)

#define FILL1(a) FILL(a,-1)

#define FILLBIG(a) FILL(a,0x3f)

#define ALL(a) (a).begin(),(a).end()

#define Inf ((int)0x3f3f3f3f)

#define INF ((long long)0x3f3f3f3f3f3f3f3f)

#define Mod 1000000007

#define foreach(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)

#define FOR(i,x) for(int i=0;i<x;i++)

#define RFOR(i,x) for(int i=x-1;i>=0;i--)

#define FFOR(i,a,b) for(int i=a;i<b;i++)

#define FRFOR(i,a,b) for(int i=a-1;i>=b;i--)

#define SZ(a) ((int)(a).size())

#define FI first

#define SE second

#define OVER(...) return printf(__VA_ARGS__),0

#define fastio ios::sync_with_stdio(0)

#define filei(f) freopen(f,"r",stdin)

#define fileo(f) freopen(f,"w",stdout)

#define eprintf(...) fprintf(stderr,__VA_ARGS__)

#define MASK(a) (1<<(a))

#define MASKX(x,a) ((x)<<(a))

#define BIT(a,b) (((a)>>(b))&1)

#define cddx(a) priority_queue<a >

#define cxdd(a) priority_queue<a,vector<a >,greater<a > >

#define deval(a) {cerr<<#a<<" = "<<a<<endl;}

#define dearr(be,en) {cerr<<#be;cerr<<" = {";for(auto i=be;i!=en;i++)cerr<<' '<<*i;cerr<<" }\n";}

#define reg register

#define prtime eprintf("\n\nTime used: %dms\n",clock());

#define PI 3.1415926535897932384626

#define TODEG(a) (a*180/PI)

#define y0 ykangjimutigeidiqiuyipianjingtu

#define y1 yxiaomiexuduhuanrenleiwannianankang

//抗击母体，给地球一片净土

//消灭徐毒，还人类万年安康

using namespace std;

typedef pair<int,int> pii;

typedef unsigned long long UINT;

typedef unsigned int uint;

typedef long long INT;

typedef long double ldouble;

typedef pair<INT,INT> PII;

typedef stringstream sst;

typedef istringstream iss;

typedef vector<int> vint;

typedef vector<INT> VINT;

typedef vector<pii> vpii;

typedef vector<PII> VPII;

typedef priority_queue<int> pqi;

typedef priority_queue<INT> PQI;

typedef priority_queue<pii> pqp;

typedef priority_queue<PII> PQP;

typedef priority_queue<int,vint,greater<int> > xqi;

typedef priority_queue<INT,VINT,greater<INT> > XQI;

typedef priority_queue<pii,vpii,greater<pii> > xqp;

typedef priority_queue<PII,VPII,greater<PII> > XQP;

inline int read()

{

	int num=0;

	char c=getchar();

	if(c=='-')return -read();

	while(c>='0'&&c<='9')

	{

		num=(num<<3)+(num<<1)+c-'0';

		c=getchar();

	}

	return num;

}

inline INT READ()

{

	INT num=0;

	char c=getchar();

	if(c=='-')return -READ();

	while(c>='0'&&c<='9')

	{

		num=(num<<3)+(num<<1)+c-'0';

		c=getchar();

	}

	return num;

}

//Coded by Charlieyan

//版权所有，翻印必究



const int N=1234567;

vector<pii> nei[N];

vector<int> hv[N];

vector<int> nnei[N];

int n,m;

int col[N];

int now[N];

int nn;

int dist[N];



int main()

{

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

    for(int i=0;i<m;i++)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        a--;b--;

        nei[a].pb(mp(c,b));

        nei[b].pb(mp(c,a));

        hv[c].pb(a);

        hv[c].pb(b);

    }

    for(int i=0;i<n;i++)

        sort(ALL(nei[i]));

    FILL1(col);

    FILL0(now);

    nn=n;

    for(int i=0;i<N;i++)

    {

        if(!SZ(hv[i]))continue;

        for(int j=0;j<SZ(hv[i]);j++)

        {

            if(col[hv[i][j]]==i)continue;

            queue<int> q;

            col[hv[i][j]]=i;

            q.push(hv[i][j]);

            nnei[nn].pb(hv[i][j]);

            nnei[hv[i][j]].pb(nn);

            while(SZ(q))

            {

                int x=q.front();

                q.pop();

                for(;now[x]<SZ(nei[x])&&nei[x][now[x]].first==i;now[x]++)

                {

                    if(col[nei[x][now[x]].second]==i)continue;

                    q.push(nei[x][now[x]].second);

                    nnei[nn].pb(nei[x][now[x]].second);

                    nnei[nei[x][now[x]].second].pb(nn);

                    col[nei[x][now[x]].second]=i;

                }

            }

            nn++;

        }

    }

    for(int i=0;i<nn;i++)

        dist[i]=-2;

    queue<int> q;

    q.push(0);

    dist[0]=0;

    while(SZ(q))

    {

        int x=q.front();

        q.pop();

        for(int i=0;i<SZ(nnei[x]);i++)

            if(dist[nnei[x][i]]==-2)

            {

                dist[nnei[x][i]]=dist[x]+1;

                q.push(nnei[x][i]);

            }

    }

    printf("%d\n",dist[n-1]/2);

    return 0;

}

// Fastest known solution for this problem: