#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 100010, M = 200010, C = 1000010, INF = 0x3f3f3f3f;

int n, m;

namespace Graph {
    int tot = -1, head[N + M];
    struct Edge {
        Edge(int p = 0, int next = 0) : p(p), next(next) {}
        int p, next;
    } edge[M << 2];
    inline void Add(int u, int v) {
        edge[++tot] = Edge(v, head[u]);
        head[u] = tot;
        return;
    }

    int dist[N + M];
    queue<int> que;
    bool exist[N + M];

    void SPFA() {
        memset(dist, 0x3f, sizeof(dist));
        dist[1] = 0;
        que.push(1);
        exist[1] = 1;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            exist[u] = 0;
            for (int i = head[u]; ~i; i = edge[i].next) {
                int v = edge[i].p;
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    if (!exist[v]) {
                        que.push(v);
                        exist[v] = 1;
                    }
                }
            }
        }
        if (dist[n] < INF) printf("%d\n", (dist[n] >> 1));
        else puts("-1");
        return;
    }
}

namespace BG {
    vector<int> col[C], app;
    int eu[M], ev[M], f[M];
    int tot = -1, head[N];
    struct Edge {
        Edge(int p = 0, int next = 0, int idx = 0) : p(p), next(next), idx(idx) {}
        int p, next, idx;
    } edge[M << 1];
    inline void Add(int u, int v, int idx) {
        edge[++tot] = Edge(v, head[u], idx);
        head[u] = tot;
        return;
    }
    bool exist[N];
    int cnt;

    void DFS(int u) {
        exist[u] = 0;
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].p;
            if (!f[edge[i].idx]) f[edge[i].idx] = cnt;
            if (exist[v]) DFS(v);
        }
        head[u] = -1;
        return;
    }

    void Main() {
        scanf("%d%d", &n, &m);
        int mc = 0;
        for (int i = 1; i <= m; ++i) {
            int c;
            scanf("%d%d%d", &eu[i], &ev[i], &c);
            col[c].push_back(i);
            if (mc < c) mc = c;
        }
        cnt = n;
        memset(head, -1, sizeof(head));
        for (int i = 1; i <= mc; ++i)
            if (col[i].size()) {
                app.clear();
                for (int j = 0; j < (int)col[i].size(); ++j) {
                    int u = eu[col[i][j]], v = ev[col[i][j]];
                    Add(u, v, col[i][j]);
                    Add(v, u, col[i][j]);
                    if (!exist[u]) {
                        app.push_back(u);
                        exist[u] = 1;
                    }
                    if (!exist[v]) {
                        app.push_back(v);
                        exist[v] = 1;
                    }
                }
                for (int j = 0; j < (int)app.size(); ++j)
                    if (exist[app[j]]) {
                        ++cnt;
                        DFS(app[j]);
                    }
            }
        memset(Graph::head, -1, sizeof(Graph::head));
        for (int i = 1; i <= m; ++i) {
            Graph::Add(eu[i], f[i]);
            Graph::Add(f[i], eu[i]);
            Graph::Add(ev[i], f[i]);
            Graph::Add(f[i], ev[i]);
        }
        return;
    }
}

int main() {
    BG::Main();
    Graph::SPFA();
    return 0;
}

Measured memory_bytes: 46208