///
/**
 * @Samaritan
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define pb emplace_back
#define fi first
#define se second
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PLI pair<LL, int>

LL quick_pow (LL a, LL b, LL mod) {
    LL ans = 1, base = a;
    while (b) {
        if (b & 1) (ans *= base) %= mod;
        b >>= 1;
        (base *= base) %= mod;
    }
    return ans;
}

inline int log2(const float &x) {
    return ((unsigned &) x >> 23 & 255) - 127;
}

void show(int arr[], int len) {
    for (int i = 0; i <= len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
struct node {
    int dif, id;
    node() {
    }
    node(int d, int i) : dif(d), id(i) {}
    bool operator < (const node& k) const {
        return dif < k.dif;
    }
};

const int mod = 998244353;
const int N = 1e5 + 5;
const int logN = 20;
const int INF = 0x3f3f3f3f;

vector<PII> edge[N];
int dist[N];
set<int> type[N];
//bool vis[N];

void work(int n) {
    priority_queue<pair<int,int> >p;
    memset(dist, INF, sizeof dist);
    p.push({0,1});dist[1]=0;
    while(!p.empty())
    {
        int now=p.top().se,ca=-p.top().fi;
        p.pop();
        if(dist[now]<ca)continue;
        for (const auto& pp : edge[now])
//        for(i=h[now];i;i=e[i].nxt)
        {
            int to=pp.first,to_com=pp.second;
            int to_ca=ca+(!type[now].count(to_com));
            if(dist[to]>to_ca)
            {
                dist[to]=to_ca;
                p.push({-to_ca,to});
                type[to].clear();
                type[to].insert(to_com);
            }
            else if(dist[to]==to_ca)
            {
                type[to].insert(to_com);
            }
        }
    }
    return;
    priority_queue<PII, vector<PII>, greater<> > pq;
    memset(dist, INF, sizeof(dist));
//    memset(vis, 0, sizeof(vis[0]) * (n + 3));
    type[1].clear();
    dist[1] = 0;
    pq.push({0, 1});

    while(!pq.empty()) {
        int now = pq.top().se, ca = pq.top().fi;
        pq.pop();
        if (dist[now] < ca)continue;
        for (const auto &p : edge[now]) {
            {
                int to = p.first, to_com = p.second;
                int to_ca = ca + (!type[now].count(to_com));
                if (dist[to] > to_ca) {
                    dist[to] = to_ca;
                    pq.push({to_ca, to});
                    type[to].clear();
                    type[to].insert(to_com);
                } else if (dist[to] == to_ca) {
                    type[to].insert(to_com);
                }
            }
        }
    }
    return;
    while (!pq.empty()) {
        int pos = pq.top().second;
        int now_dist = pq.top().first;
        pq.pop();
//        if (vis[pos]) continue;
//        vis[pos] = true;
        if (now_dist > dist[pos]) continue;
        for (const auto& p : edge[pos]) {
            int to = p.first;
            int now_type = p.second;
            int now_val = dist[pos];
            if (!type[pos].count(now_type))
                now_val++;
            if (now_val < dist[to]) {
                dist[to] = now_val;
                type[to].clear();
                type[to].insert(now_type);

                pq.push({dist[to], to});
            } else if (now_val == dist[to]) {
                type[to].insert(now_type);
            }
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; ++i)
        edge[i].clear();
    int l, r, c;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &l, &r, &c);
        edge[l].pb(r, c);
        edge[r].pb(l, c);
    }
    work(n);
    
    if (dist[n] >= INF)
        puts("-1");
    else
        printf("%d\n", dist[n]);
    return 0;
}


Measured memory_bytes: 23412