#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100010
#define MAX_M 200010
#define MAX_C 1000010

template <typename IndexType, typename CostType>
class Dijkstra {
    private:
        struct Edge {
            IndexType to;      // 有向辺の行先頂点
            CostType cost;    // 辺の重み
        };
        typedef pair<CostType, IndexType> P;       // first: 最短距離 second: 頂点 id
    public:
        Dijkstra(IndexType v, CostType inf, bool isEnablePath) : m_V(v), m_Inf(inf), m_IsEnablePath(isEnablePath) {
            m_G = new vector<Edge>[m_V];
            m_D = new CostType[m_V];
            if(m_IsEnablePath) { m_PrevP = new IndexType[m_V]; }
        }
        ~Dijkstra() {
            delete[] m_G;
            delete[] m_D;
            if(m_IsEnablePath) { delete[] m_PrevP; }
        }
        // 有向辺の追加
        void AddDirEdge(IndexType from, IndexType to, CostType cost) { m_G[from].push_back({to, cost}); }
        // 無向辺の追加
        void AddUndirEdge(IndexType from, IndexType to, CostType cost) {
            AddDirEdge(from, to, cost);
            AddDirEdge(to, from, cost);
        }
        // 始点 s から各頂点への最短経路の導出 O(E log V)
        void Calc(IndexType s) {
            // greater<P>を指定することでfirstが小さい順に取り出せるようにする
            priority_queue<P, vector<P>, greater<P> > que;
            fill(m_D, m_D + m_V, m_Inf);
            if(m_IsEnablePath) { fill(m_PrevP, m_PrevP + m_V, -1); }
            m_D[s] = 0;
            que.push(P(0, s));
            while(!que.empty()) {
                P p = que.top(); que.pop();
                IndexType v = p.second;
                if(m_D[v] < p.first){ continue; }
                for(int i = 0; i < m_G[v].size(); ++i) {
                    Edge e = m_G[v][i];
                    if(m_D[e.to] > m_D[v] + e.cost) {
                        m_D[e.to] = m_D[v] + e.cost;
                        if(m_IsEnablePath) { m_PrevP[e.to] = v; }
                        que.push(P(m_D[e.to], e.to));
                    }
                }
            }
        }
        // 始点 s から頂点 t への最短距離を返す O(1)
        // 前処理として Calc(s) が必要
        CostType GetDist(IndexType t) { return m_D[t]; }
        // 始点 s から頂点 t までの経路を vector に入れて返す (s と t 含む)
        // O(V') … V' は最短経路の頂点数
        // 前処理として Calc(s) が必要
        vector<IndexType> GetPath(IndexType t) {
            assert(m_IsEnablePath);
            vector<IndexType> path;
            for(; t != -1; t = m_PrevP[t]) { path.push_back(t); }  // t が s になるまで prev_p[t] を辿っていく
            // このままだと t->s の順になっているので逆順にする
            reverse(path.begin(), path.end());
            return path;
        }
    private:
        const IndexType m_V;                // 頂点の数
        const CostType m_Inf;              // 無限の代わりとして扱う値
        const bool m_IsEnablePath;  // 経路も求める場合は true
        vector<Edge>* m_G;          // 頂点 i から延びている辺の隣接リスト
        CostType* m_D;                     // 各頂点への最短コストが入る配列
        IndexType* m_PrevP;                 // 最短経路の各頂点を保存
};


ll N, M;
ll P[MAX_M];
ll Q[MAX_M];
ll C[MAX_M];

map< pair<int, int>, int> toId; // (現在いる駅, 最後に使った会社) の組から頂点 id を出す
vector< pair<int, int> > graph[MAX_N];  // i から出る行先 first 会社 second の辺

signed main()
{
    cin >> N >> M;
    REP(i, M) {
        scanf("%lld %lld %lld", &P[i], &Q[i], &C[i]);
        P[i]--; Q[i]--;
        graph[P[i]].push_back({Q[i], C[i]});
        graph[Q[i]].push_back({P[i], C[i]});
    }

    // toId の作成
    set< pair<int, int> > tmp;  // ノードの会社の全パターン
    REP(i, N) {
        tmp.insert(make_pair(i, -1));
        for(auto& node : graph[i]) {
            tmp.insert(make_pair(i, node.second));
        }
    }
    int id = 0;
    for(auto& t : tmp) {
        toId[t] = id;
        id++;
    }

    // グラフの作成
    Dijkstra<int, int> dk(id, INF, false);

    REP(i, N) {
        set<int> co;    // このノードから延びている会社の種類
        for(auto& node : graph[i]) {
            co.insert(node.second);
            // 同じ会社の路線ならコスト 0
            int from = toId[make_pair(i, node.second)];
            int to = toId[make_pair(node.first, node.second)];
            dk.AddDirEdge(from, to, 0);
        }
        for(auto& c : co) {
            // 違う会社の路線に乗るなら一旦 -1 に集合
            int from = toId[make_pair(i, c)];
            int to = toId[make_pair(i, -1)];
            dk.AddDirEdge(from, to, 0);
            // そこからコスト 1 で別路線に乗れる
            dk.AddDirEdge(to, from, 1);
        }
    }

    int st = toId[make_pair(0, -1)];
    int gl = toId[make_pair(N-1, -1)];

    dk.Calc(st);
    int ans = dk.GetDist(gl);
    if(ans == INF) { ans = -1; }
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 131444