Problem: Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

* 2 \leq N \leq 10^5
* 0 \leq M \leq 2×10^5
* 1 \leq p_i \leq N (1 \leq i \leq M)
* 1 \leq q_i \leq N (1 \leq i \leq M)
* 1 \leq c_i \leq 10^6 (1 \leq i \leq M)
* p_i \neq q_i (1 \leq i \leq M)

Input

The input is given from Standard Input in the following format:


N M
p_1 q_1 c_1
:
p_M q_M c_M


Output

Print the minimum required fare. If it is impossible to get to station N by subway, print `-1` instead.

Examples

Input

3 3
1 2 1
2 3 1
3 1 2


Output

1


Input

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5


Output

2


Input

2 0


Output

-1

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

vector<int> g[512512][2];
deque<int> dq;
map<P, int> mp;
int dist[512512];
bool done[512512];

int main(void){
	int n,m,u,v,c,i,p,q,vtx;
	fill(dist,dist+512512,INF);
	cin >> n >> m; vtx = n;
	for(i=0; i<m; ++i){
		cin >> u >> v >> c;
		--u; --v;
		if(mp.find(P(u,c)) == mp.end()){
			mp[P(u,c)] = vtx; ++vtx;
		}
		p = mp[P(u,c)];
		if(mp.find(P(v,c)) == mp.end()){
			mp[P(v,c)] = vtx; ++vtx;
		}
		q = mp[P(v,c)];
		g[u][1].push_back(p);
		g[v][1].push_back(q);
		g[p][0].push_back(u);
		g[q][0].push_back(v);
		g[p][0].push_back(q);
		g[q][0].push_back(p);
	}
	dist[0] = 0;
	dq.push_back(0);
	while(!dq.empty()){
		u = dq.front();
		dq.pop_front();
		for(c=0; c<2; ++c){
			for(i=(g[u][c].l_ength()-1); i>=0; --i){
				v = g[u][c][i];
				if(dist[v] > dist[u]+c){
					dist[v] = dist[u]+c;
					if(c){
						dq.push_back(v);
					}else{
						dq.push_front(v);
					}
				}
			}
		}
	}
	cout << ((dist[n-1]<INF)?dist[n-1]:(-1)) << endl;
	return 0;
}