//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define mk make_pair
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
//#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
template<typename T>
inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>
inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=7e5+10,maxn=4000000+10,inf=0x3f3f3f3f;

int n, m, tot, head[N], all, d[N];

struct Edge {
    int u, v, w, nx;
} edge[4000000];

struct node {
    int u, v, w, id;
    bool operator < (const node &rhs) const {
        return w < rhs.w;
    }
} a[N];

vector<node> vec[N];

void add(int u, int v, int w) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].nx = head[u];
    head[u] = tot++;
}

void init() {
    all = m + 1; tot = 0;
    memset(head, -1, sizeof(head));
    memset(d, inf, sizeof(d));
    for(int i = 1; i <= n; i++) vec[i].clear();
}

int Dij(int S, int T) {
    priority_queue<pii, vector<pii>, greater<pii> > que;
    d[S] = 0; que.push(mk(0, S));
    while(!que.empty()) {
        pii now = que.top(); que.pop();
        int u = now.se, val = now.fi;
        if(val < d[u]) continue;
        for(int i = head[u]; ~i; i = edge[i].nx) {
            int v = edge[i].v, w = edge[i].w;
            if(val + w < d[v]) {
                d[v] = val + w;
                que.push(mk(d[v], v));
            }
        }
    }
    return d[T];
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        init();
        for(int i = 1; i <= m; i++) {
            scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
            a[i].id = i;
            vec[a[i].u].push_back(a[i]);
            vec[a[i].v].push_back(a[i]);
        }
        for(int i = 1; i <= n; i++) {
            sort(vec[i].begin(), vec[i].end());
            int root = ++all;
            for(int j = 0; j < vec[i].size(); j++) {
                add(root, vec[i][j].id, 1);
                add(vec[i][j].id, root, 1);
                if(!j || vec[i][j].w != vec[i][j - 1].w) ++all;
                add(all, vec[i][j].id, 0);
                add(vec[i][j].id, all, 0);
            }
        }

        for(int i = 1; i <= m; i++) {
            if(a[i].u == 1 || a[i].v == 1) {
                add(0, a[i].id, 2);
                add(a[i].id, 0, 2);
            }
            if(a[i].u == n || a[i].v == n) {
                add(m + 1, a[i].id, 0);
                add(a[i].id, m + 1, 0);
            }
        }

        int ans = Dij(0, m + 1);
        if(ans == inf) puts("-1");
        else printf("%d\n", ans / 2);
    }
    return 0;
}
/********************
4 4
1 2 1
1 3 1
2 4 1
3 4 1
********************/


Measured memory_bytes: 70128