#include <bits/stdc++.h>
using namespace std;
#define mem(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,-1,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define endl "\n"
typedef long long ll;
inline int rint() { int a; scanf("%d", &a); return a; }
inline long long rll() { long long a; scanf("%lld", &a); return a; }
inline double rdouble() { double a; scanf("%lf", &a); return a; }
ll gcd(ll a, ll b) { return (b) ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
ll pow(ll a, ll b, ll q) { ll k = a; ll ans = 1; while (b) { if (b & 1) ans = ans * k%q; k = k * k%q; b >>= 1; }return ans; }
ll countOnes(ll x) { ll c = 0; for (; x; x >>= 1) c += x & 1; return c; }
const double eps = 1e-9;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const int N = 600005;

int father[N];
void build(int n) { for (int i = 0; i < n; i++) father[i] = i; }
int findroot(int in) { return father[in] == in ? in : father[in] = findroot(father[in]); }
void merge(int x, int y) { if (findroot(x) == findroot(y)) return;    father[findroot(x)] = findroot(y); }

vector<pair<int, int>> fei[1000005];
vector<int> v[N];
int vis[N];
int res[N];
int gen[N];

#define FI(n) FastIO::read(n)
namespace FastIO {
    const int SIZE = 1 << 16;
    char buf[SIZE], obuf[SIZE], str[60];
    int bi = SIZE, bn = SIZE, opt;
    int read(char *s) {
        while (bn) {
            for (; bi < bn && buf[bi] <= ' '; bi++);
            if (bi < bn) break;
            bn = fread(buf, 1, SIZE, stdin);
            bi = 0;
        }
        int sn = 0;
        while (bn) {
            for (; bi < bn && buf[bi] > ' '; bi++) s[sn++] = buf[bi];
            if (bi < bn) break;
            bn = fread(buf, 1, SIZE, stdin);
            bi = 0;
        }
        s[sn] = 0;
        return sn;
    }
    bool read(int& x) {
        int n = read(str), bf;
        if (!n) return 0;
        int i = 0; if (str[i] == '-') bf = -1, i++; else bf = 1;
        for (x = 0; i < n; i++) x = x * 10 + str[i] - '0';
        if (bf < 0) x = -x;
        return 1;
    }
};

int main() {
    //freopen("1.in", "r", stdin);
    int n, m; while (FI(n)) {
        FI(m);
        for (int i = 1; i <= 1000000; i++) fei[i].clear();
        for (int i = 1; i <= n; i++) v[i].clear();
        while (m--) {
            //int s = rint(), t = rint(), w = rint();
            int s, t, w; FI(s); FI(t); FI(w);
            fei[w].push_back(make_pair(s, t));
        }
        int cnt = n;
        for (int k = 1; k <= 1000000; k++) {
            if (fei[k].size() == 0) continue;
            vector<int> temp;
            for (int i = 0; i < fei[k].size(); i++) temp.push_back(fei[k][i].first);
            for (int i = 0; i < fei[k].size(); i++) temp.push_back(fei[k][i].second);
            sort(all(temp)); temp.erase(unique(all(temp)), temp.end());
            for (int i = 0; i < temp.size(); i++) father[temp[i]] = temp[i];
            for (int i = 0; i < fei[k].size(); i++) merge(fei[k][i].first, fei[k][i].second);

            vector<int> fa;
            for (int i = 0; i < temp.size(); i++) fa.push_back(findroot(temp[i]));
            sort(all(fa)); fa.erase(unique(all(fa)), fa.end());
            for (int i = 0; i < fa.size(); i++) { gen[fa[i]] = ++cnt; v[cnt].clear(); }
            for (int i : temp) {
                v[i].push_back(gen[findroot(i)]);
                v[gen[findroot(i)]].push_back(i);
            }
        }

        res[1] = 0; for (int i = 2; i <= cnt; i++) res[i] = inf;
        vis[1] = 1; for (int i = 2; i <= cnt; i++) vis[i] = 0;
        queue<int> q; q.push(1);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int j = 0; j < v[x].size(); j++) {
                if (vis[v[x][j]] == 1) continue;
                res[v[x][j]] = res[x] + 1;
                q.push(v[x][j]);
                vis[v[x][j]] = 1;
            }
        }
        if (res[n] != inf) printf("%d\n", res[n] / 2);
        else puts("-1");
    }
}

Measured memory_bytes: 59776