#define LOCAL

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>

using namespace std;

// From Errichto's Youtube stream
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using int64 = long long;

/////////////////////
// Code starts here//
/////////////////////

int N, M, ID;
vector<vector<pair<int, int>>> g;
map<pair<int, int>, int> cache;
vector<vector<int>> edges;
deque<int> deq;

//pair<int, int> node[1<<22];
vector<int> visited;

const int INF = (1<<30);

int GetID(int p, int c) {
    pair<int, int> key = {p, c};
    if (cache.count(key))
        return cache[key];
    
    //node[ID] = key;
    return cache[key] = ID++;
}

void AddEdge(int p, int q, int c, int index) {
    // Switch node p, p
    auto switch_p = GetID(p, 0);
    auto switch_q = GetID(q, 0);

    // Edge to switch node
    edges.push_back({index, switch_p, 1});
    edges.push_back({index, switch_q, 1});

    // Edgest to col node
    auto col_p_c = GetID(p, c);
    auto col_q_c = GetID(q, c);

    edges.push_back({index, col_p_c, 0});
    edges.push_back({index, col_q_c, 0});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    ID = M;

    GetID(0, 0);
    GetID(N - 1, 0);

    for (int i = 0; i < M; i++) {
        int p, q, c;
        cin >> p >> q >> c;
        p--, q--;
    
        AddEdge(p, q, c, i);
        AddEdge(q, p, c, i);
    }

    g.resize(ID);
    visited = vector<int>(ID, INF);

    for (auto e : edges) {
        g[e[0]].emplace_back(e[1], e[2]);
        g[e[1]].emplace_back(e[0], e[2]);
    }

    int result = -1;

    auto start = GetID(0, 0);
    auto finish = GetID(N - 1, 0);

    visited[start] = 0;

    for (deq.push_back(start); !deq.empty(); ) {
        auto el = deq.front();
        deq.pop_front();

        auto dist = visited[el];

        //debug() << (el < M ? make_pair(el, -1) : node[el]) << " " << dist;

        if (el == finish) {
            //debug() << dist;
            result = dist;
            break;
        }

        for (auto p : g[el]) {
            auto v = p.first;
            auto cost = p.second;
            if (visited[v] == INF) {
                //debug() << " -> " << v << "\n";
                if (cost) {
                    visited[v] = dist + 1;
                    deq.push_back(v);
                } else {
                    visited[v] = dist;
                    deq.push_front(v);
                }
            }
        }

        visited[el] = -1;
    }

    if (result == -1) {
        cout << -1 << "\n";
    } else {
        cout << (result - 1) / 2 + 1 << "\n";
    }

    return 0;
}


Measured memory_bytes: 178080