1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define LL long long
 4 using namespace std;
 5 
 6 const int MAXN = 1e5+10;
 7 bool vis[MAXN];
 8 int N, M;
 9 
10 struct Edge
11 {
12     int nxt, no, v;
13 }edge[MAXN<<2];
14 int head[MAXN], tot;
15 void init()
16 {
17     memset(vis, 0, sizeof(vis));
18     memset(head, -1, sizeof(head));
19     tot = 0;
20 }
21 
22 void add(int a, int b, int no)
23 {
24     edge[tot].v = b;
25     edge[tot].no = no;
26     edge[tot].nxt = head[a];
27     head[a] = tot++;
28 }
29 
30 struct data
31 {
32     int u, v, cnt, type;
33     bool operator < (const data &a) const {
34         return cnt > a.cnt;
35     }
36 };
37 
38 
39 int solve()
40 {
41     data x, y;
42     int from, to, t, vv, sum;
43     priority_queue<data>quq;
44     for(int i = head[1]; i != -1; i = edge[i].nxt){
45         x.u = 1;
46         x.v = edge[i].v;
47         x.cnt = 1;
48         x.type = edge[i].no;
49         quq.push(x);
50     }
51     vis[1] = true;
52     while(!quq.empty()){
53         x = quq.top();
54         quq.pop();
55         to = x.v;
56         t = x.type;
57         sum = x.cnt;
58         if(to == N) return sum;
59         vis[to] = true;
60         for(int i = head[to]; i != -1; i = edge[i].nxt){
61             vv = edge[i].v;
62             if(vis[vv]) continue;
63             if(edge[i].no != t) y.cnt = sum+1;
64             else y.cnt = sum;
65             y.v = vv;
66             y.type = edge[i].no;
67             quq.push(y);
68         }
69     }
70     return -1;
71 }
72 
73 int main()
74 {
75     int u, v, no;
76     while(~scanf("%d %d", &N, &M)){
77         init();
78         for(int i = 1; i <= M; i++){
79             scanf("%d %d %d", &u, &v, &no);
80             add(u, v, no);
81             add(v, u, no);
82         }
83 
84         int ans = solve();
85         printf("%d\n", ans);
86     }
87     return 0;
88 }