#include <bits/stdc++.h>

#define LL long long
#define VI vector<int>
#define VB vector<bool>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14
#define MINUS(a) memset(a,0xff,sizeof(a))

const std::string YES = "YES";
const std::string Yes = "Yes";
const std::string NO = "NO";
const std::string No = "No";

using namespace std;


void dfs(int station, int company, vector<int> &sta, vector<vector<int>> &station_graph, vector<int> &used) {
    if (used[station] == company) {
        return;
    }
    used[station] = company;
    sta.emplace_back(station);

    FOE(to_station,station_graph[station]) {
        dfs(to_station, company, sta, station_graph, used);
    }
}


void solve(int N, int M, vector<int> &P, vector<int> &Q, vector<int> &C) {
    int num_of_company = 1010101;

    vector<vector<pair<int,int>>> company_station(num_of_company);
    FOR(i, 0, M) {
        company_station[C[i]].emplace_back(make_pair(P[i], Q[i]));
    }

    vector<int> graph[303030 + 1];
    int id = N + 1;
    vector<int> used(num_of_company, -1);
    vector<vector<int>> station_graph(N + 1);
    FOR(company, 0, num_of_company) {
        if(company_station[company].empty()) { continue; }

        vector<int> station_list;   // 現在処理しているcompanyに所属している駅のリスト
        FOE(e, company_station[company]) {
            station_graph[e.first].push_back(e.second);
            station_graph[e.second].push_back(e.first);

            station_list.push_back(e.first);
            station_list.push_back(e.second);
        }

        FOE(station, station_list) {
            if(used[station] == company) { continue; }

            vector<int> sta;
            dfs(station, company, sta, station_graph, used);
            FOE(s, sta) {
                graph[id].push_back(s);
                graph[s].push_back(id);
            }

            id++;
        }

        FOE(e, company_station[company]) {
            station_graph[e.first].clear();
            station_graph[e.second].clear();
        }
    }

    vector<int> dist(303030, INT_MAX);
    dist[1] = 0;
    queue<int> que;
    que.push(1);
    while (not que.empty()) {
        int x = que.front();que.pop();
        FOE(e, graph[x]) {
            if(dist[e] > dist[x] + 1) {
                dist[e] = dist[x] + 1;
                que.push(e);
            }
        }
    }

    int ans = dist[N];
    cout << (ans == INT_MAX ? -1 : ans / 2) << endl;

}

int main() {
    int N, M, num_of_company = 0;
    cin >> N >> M;
    vector<int> P(M), Q(M), C(M);

    FOR(i, 0, M) {
        cin >> P[i] >> Q[i] >> C[i];
    }
    solve(N, M, P, Q, C);

    return 0;
}

Measured memory_bytes: 59904