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:
// 0-1 BFS with virtual vertices
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define Map unordered_map
using namespace std;

int n,m;
Map<ll,vector<pair<ll,int>>> adj;
Map<ll,int> d;
Map<ll,bool> vst;

ll id(int x,int y){
	return 100000000LL*x+y;
}

int main() {
	#ifdef kvutxdy
	freopen("C:/Users/khanh/OneDrive/RoadtoPurple/Code/Codeforces/input.in", "r", stdin);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=0;i<m;++i){
		int u,v,c;
		cin>>u>>v>>c;
		adj[id(u,c)].push_back({id(v,c),0});
		adj[id(v,c)].push_back({id(u,c),0});
		adj[id(u,c)].push_back({id(u,0),0});
		adj[id(u,0)].push_back({id(u,c),1});
		adj[id(v,c)].push_back({id(v,0),0});
		adj[id(v,0)].push_back({id(v,c),1});
	}
	deque<ll> dq;
	d[id(1,0)]=0;
	dq.push_front(id(1,0));
	while(!dq.empty()){
		ll u=dq.front();
		dq.pop_front();
		vst[u]=true;
		for(auto nxt:adj[u]){
			ll v=nxt.fi;
			int c=nxt.se;
			if(vst.count(v)) continue;
			if(!d.count(v)||d[u]+c<d[v]){
				d[v]=d[u]+c;
				if(c==0) dq.push_front(v);
				else dq.push_back(v);
			}
		}
	}
	if(!d.count(id(n,0))) cout<<-1;
	else cout<<d[id(n,0)];
}