#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <map>

using namespace std;

template< typename T >
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;

template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s) {
    const auto INF = numeric_limits< T >::max();
    vector< T > dist(g.size(), INF);

    using Pi = pair< T, int >;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    dist[s] = 0;
    que.emplace(dist[s], s);
    while(!que.empty()) {
        T cost;
        int idx;
        tie(cost, idx) = que.top();
        que.pop();
        if(dist[idx] < cost) continue;
        for(auto &e : g[idx]) {
            auto next_cost = cost + e.cost;
            if(dist[e.to] <= next_cost) continue;
            dist[e.to] = next_cost;
            que.emplace(dist[e.to], e.to);
        }
    }
    return dist;
}

struct UnionFind {
    vector< int > data;

    UnionFind(int sz) {
        data.assign(sz, -1);
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return (false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }

    int find(int k) {
        if(data[k] < 0) return (k);
        return (data[k] = find(data[k]));
    }

    int size(int k) {
        return (-data[find(k)]);
    }
};

template< typename T >
struct Compress {
    vector< T > xs;

    Compress() = default;

    Compress(const vector< T > &vs) {
        add(vs);
    }

    Compress(const initializer_list< vector< T > > &vs) {
        for(auto &p : vs) add(p);
    }

    void add(const vector< T > &vs) {
        copy(begin(vs), end(vs), back_inserter(xs));
    }

    void add(const T &x) {
        xs.emplace_back(x);
    }

    void build() {
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }

    vector< int > get(const vector< T > &vs) const {
        vector< int > ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
            return lower_bound(begin(xs), end(xs), x) - begin(xs);
        });
        return ret;
    }

    int get(const T &x) const {
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }

    const T &operator[](int k) const {
        return xs[k];
    }
};

int main(void) {
    int N, M;
    cin >> N >> M;
    map< int, vector<pair<int,int>> > mp;
    for(int j=0; j<M; j++) {
        int p, q, c;
        cin >> p >> q >> c;
        mp[c].emplace_back(--p, --q);
    }

    vector<int> P, Q;
    vector<int64_t> C;
    for(auto e: mp) {
        int64_t c = e.first;
        c *= 10'000'000;
        if(e.second.size() == 1) {
            P.emplace_back(e.second.front().first);
            Q.emplace_back(e.second.front().second);
            C.emplace_back(c);
            continue;
        }
        UnionFind uf(N);
        for(auto edge: e.second) {
            int p = edge.first;
            int q = edge.second;
            uf.unite(p, q);
        }
        for(auto edge: e.second) {
            int p = edge.first;
            int q = edge.second;
            P.emplace_back(p);
            Q.emplace_back(q);
            C.emplace_back(c + uf.find(p));
        }
    }

    Compress<int64_t> comp(C);
    comp.build();

    WeightedGraph<int> g(300000);
    for(int j=0; j<M; j++) {
        int c = 100'000 + comp.get(C[j]);
        g[P[j]].emplace_back(c, 1);
        g[Q[j]].emplace_back(c, 1);
        g[c].emplace_back(P[j], 0);
        g[c].emplace_back(Q[j], 0);
    }

    int d = dijkstra(g, 0)[N-1];
    if(d == numeric_limits<int>::max()) {
        cout << -1 << endl;
    } else {
        cout << d << endl;
    }

    return 0;
}


Measured memory_bytes: 48300