#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

struct Edge {
    int to;
    int c;
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int p, q, c;
        cin >> p >> q >> c;
        p--;
        q--;
        graph[p].push_back((Edge){q, c});
        graph[q].push_back((Edge){p, c});
    }

    for (int i = 0; i < n; ++i) {
        sort(graph[i].begin(), graph[i].end(), [](auto& a, auto& b) {
            return a.c == b.c ? a.to < b.to : a.c < b.c;
        });
    }

    map<pair<int, int>, int> dist;
    dist[{0, -1}] = 0;

    deque<pair<int, int>> que;
    deque<int> que2;
    que.emplace_back(0, -1);
    que2.push_back(0);
    while (!que.empty()) {
        auto cur = que.front();
        que.pop_front();

        auto d = que2.front();
        que2.pop_front();

        if (cur.first == n - 1) {
            cout << dist[{cur.first, cur.second}] << endl;
            return 0;
        }

        if (d > dist[cur]) continue;

        // d = dist[cur];

        if (cur.second == -1) {
            for (auto& e : graph[cur.first]) {
                if (!dist.count({e.to, e.c})) {
                    dist[{e.to, e.c}] = d + 1;
                    que.emplace_back(e.to, e.c);
                    que2.push_back(dist[{e.to, e.c}]);
                } else if (dist[{e.to, e.c}] > d + 1) {
                    dist[{e.to, e.c}] = d + 1;
                    que.emplace_back(e.to, e.c);
                    que2.push_back(dist[{e.to, e.c}]);
                }
            }
        } else {
            auto r = equal_range(graph[cur.first].begin(),
                                 graph[cur.first].end(), (Edge){0, cur.second},
                                 [](auto& a, auto& b) { return a.c < b.c; });

            for (auto it = r.first; it != r.second; ++it) {
                auto e = *it;
                if (!dist.count({e.to, e.c})) {
                    dist[{e.to, e.c}] = d;
                    que.emplace_front(e.to, e.c);
                    que2.push_front(dist[{e.to, e.c}]);
                } else if (dist[{e.to, e.c}] > d) {
                    dist[{e.to, e.c}] = d;
                    que.emplace_front(e.to, e.c);
                    que2.push_front(dist[{e.to, e.c}]);
                }
            }

            if (r.second - r.first != graph[cur.first].size()) {
                if (!dist.count({cur.first, -1})) {
                    dist[{cur.first, -1}] = d;
                    que.emplace_front(cur.first, -1);
                    que2.push_front(dist[{cur.first, -1}]);
                } else if (dist[{cur.first, -1}] > d) {
                    dist[{cur.first, -1}] = d;
                    que.emplace_front(cur.first, -1);
                    que2.push_front(dist[{cur.first, -1}]);
                }
            }
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 29824