#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

struct Link {
    int64_t id;
    int64_t src;
    int64_t dst;
    int64_t company;
};

main() {
    int64_t n, m;
    cin >> n >> m;

    vector<Link> links;
    vector<unordered_map<int64_t, vector<int64_t>>> out_links(n);
    vector<unordered_map<int64_t, int64_t>> costs(n);
    for (auto i : irange(0L, m)) {
        int64_t p, q, c;
        cin >> p >> q >> c;
        --p;
        --q;
        links.push_back(Link{2 * i, p, q, c});
        links.push_back(Link{2 * i + 1, q, p, c});
        out_links[p][c].push_back(2 * i);
        out_links[q][c].push_back(2 * i + 1);
        costs[p][c] = numeric_limits<int64_t>::max();
        costs[q][c] = numeric_limits<int64_t>::max();
    }

    vector<vector<pair<int64_t, int64_t>>> bucket(2);
    // node_id => company_id => cost
    vector<int64_t> node_costs(n, numeric_limits<int64_t>::max());
    for (const auto& kv : out_links[0]) {
        for (auto link_id : kv.second) {
            const auto& link = links[link_id];
            costs[link.dst][link.company] = 1;
            bucket[1].emplace_back(1, link_id);
        }
    }
    node_costs[0] = 0;

    int64_t cost = 1;
    while (!(bucket[0].empty() && bucket[1].empty())) {
        if (bucket[cost % 2].empty()) {
            ++cost;
            continue;
        }

        auto link_id = bucket[cost % 2].back().second;
        bucket[cost % 2].pop_back();

        const auto& current_link = links[link_id];

        if (cost > costs[current_link.dst][current_link.company]) {
            continue;
        }

        // prune
        if (node_costs[current_link.dst] < cost) {
            // 逆転不可
            continue;
        } else if (node_costs[current_link.dst] == cost) {
            // 同じ会社のところだけ調べればよい
            for (auto next_link_id :
                 out_links[current_link.dst][current_link.company]) {
                const auto& next_link = links[next_link_id];
                auto next_cost = cost;

                if (next_cost < costs[next_link.dst][next_link.company]) {
                    costs[next_link.dst][next_link.company] = next_cost;
                    bucket[next_cost % 2].emplace_back(next_cost, next_link.id);
                }
            }

            continue;
        }

        node_costs[current_link.dst] = cost;

        if (current_link.dst == n - 1) {
            cout << cost << endl;
            return 0;
        }

        for (const auto& kv : out_links[current_link.dst]) {
            for (auto next_link_id : kv.second) {
                const auto& next_link = links[next_link_id];
                auto next_cost =
                        cost +
                        (current_link.company == next_link.company ? 0 : 1);

                if (next_cost < costs[next_link.dst][next_link.company]) {
                    costs[next_link.dst][next_link.company] = next_cost;
                    bucket[next_cost % 2].emplace_back(next_cost, next_link.id);
                }
            }
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 87652