#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include <fstream>
#include <time.h>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
//#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

int MAX = 100010;
int MOD = (ll)1000000000 + 7;
ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;


typedef pair<ll, int>P;//firstは距離、secondは頂点番号
struct Ver { ll dist; set<int>company; };//頂点に、始点からの距離と最後に使った会社を持たせる
struct edge { int to, cmp; };//辺には行き先の頂点と会社を持たせる
Ver d[100010];
int V;//頂点数
int M;//辺の本数

vector<edge>G[100010];//グラフ
					  //int d[MAX];//始点からの距離
void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P>>que;
	set<int>st;//キューに入っている頂点番号
	//全点への距離をINFで初期化
	for (int i = 0; i < V + 1; i++) {
		d[i].dist = INF;
	}
	//始点への距離は0
	d[s].dist = 0;
	//始点をキューに入れる
	que.push(P(0, s)); st.insert(s);
	while (!que.empty()) {
		P p = que.top(); que.pop();
		auto c = st.erase(p.second);
		int v = p.second;//今見ている頂点
		if (d[v].dist < p.first)continue;

		//今見ている頂点につながるすべての辺について距離を更新する
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			int cost = 1;
			//vに訪れるのに最後に使った会社(複数の場合もある)が今見ている辺の会社と同じならコストを0にする
			if (d[v].company.find(e.cmp) != d[v].company.end())cost = 0;
			//今見ている辺を使うことでe.toへの距離が小さくなるなら、距離を更新し、最後に使った会社をe.cmpとする
			if (d[e.to].dist > d[v].dist + cost) {
				d[e.to] = { d[v].dist + cost,{ e.cmp } };
				que.push(P(d[e.to].dist, e.to)); st.insert(e.to);
			}
			//今見ている辺を使っても距離が変わらない場合、最後に使った会社に(もしe.cmpがなかったら)e.cmpを追加する
			else if (d[e.to].dist == d[v].dist + cost) {
				if (d[e.to].company.find(e.cmp) == d[e.to].company.end()) {
					d[e.to].company.insert(e.cmp);
					if (st.find(e.to) == st.end()) {
						que.push(P(d[e.to].dist, e.to)); st.insert(e.to);
					}
				}

			}
		}
	}
}

int main() {
	//std::ifstream in("22.txt");
	//std::cin.rdbuf(in.rdbuf());
	
	cin >> V >> M;
	//CFileTime cTimeStart, cTimeEnd;
	//CFileTimeSpan cTimeSpan;
	//cTimeStart = CFileTime::GetCurrentTime();           // 現在時刻
	int p, q, c;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &p, &q, &c);
		G[p].push_back({ q,c });
		G[q].push_back({ p,c });
	}
	dijkstra(1);
	//cout << "dijkstra" << endl;
	ll ans = d[V].dist;
	if (ans == INF) {
		cout << -1 << endl; return 0;
	}
	cout << ans << endl;
	//cTimeEnd = CFileTime::GetCurrentTime();           // 現在時刻
	//cTimeSpan = cTimeEnd - cTimeStart;
	//std::cout << "処理時間:" << cTimeSpan.GetTimeSpan() / 10000 << "[ms]" << std::endl;
}

Measured memory_bytes: 26992