Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting ofNN ports and MM shipping lines. The ports are numbered 11 to NN. Each line is occupied by a Weitian. Each Weitian has an identification number. 

The ii-th (1≤i≤M)(1≤i≤M) line connects port AiAi and BiBi (Ai≠Bi)(Ai≠Bi) bidirectionally, and occupied by CiCi Weitian (At most one line between two ports). 

When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is 11XiangXiangJi. Whenever Mr.Quin changes to a line that is occupied by a different Weitian from the current line, Mr.Quin is charged an additional cost of 11XiangXiangJi. In a case where Mr.Quin changed from some Weitian AA's line to another Weitian's line changes to Weitian AA's line again, the additional cost is incurred again. 

Mr.Quin is now at port 11 and wants to travel to port NN where live many fishes. Find the minimum required XiangXiangJi (If Mr.Quin can’t travel to port NN, print −1−1instead)

Input

There might be multiple test cases, no more than 2020. You need to read till the end of input. 

For each test case,In the first line, two integers NN (2≤N≤100000)(2≤N≤100000) and MM (0≤M≤200000)(0≤M≤200000), representing the number of ports and shipping lines in the city. 

In the following m lines, each contain three integers, the first and second representing two ends AiAi and BiBi of a shipping line (1≤Ai,Bi≤N)(1≤Ai,Bi≤N) and the third representing the identification number CiCi (1≤Ci≤1000000)(1≤Ci≤1000000) of Weitian who occupies this shipping line.

Output

For each test case output the minimum required cost. If Mr.Quin can’t travel to port NN, output −1−1 instead.

Sample Input

3 3 
1 2 1
1 3 2
2 3 1
2 0
3 2
1 2 1
2 3 2

Sample Output

1
-1
2

 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 200005;
const int maxm = 800005;
#define inf 0x3f3f3f3f
struct edge
{
	int to, ne, len;
}ed[maxm];
int d[maxn]; int cnt = 0;//计数
int m, n; int head[maxn];
struct *** {
	int u, pre, cost;
	bool operator < (const *** &a)const {
		return cost > a.cost;
	}
	***(int v, int pre, int cost) :u(v), cost(cost), pre(pre) {}
};
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int from, int to, int len) {
	ed[cnt].to = to; ed[cnt].len = len;
	ed[cnt].ne = head[from]; head[from] = cnt++;
}
int spfa() {
	priority_queue<***>q;
	for (int s = 1; s <= n; s++)
		d[s] = inf;
	q.push(***(1, -1, 0));
	d[1] = 0;
	while (!q.empty()) {
		*** t = q.top(); q.pop();
		if (t.cost > d[t.u])continue;
		if (t.u == n)return t.cost;
		for (int s = head[t.u]; ~s; s = ed[s].ne) {
			int w;
			if (ed[s].len == t.pre)w = d[t.u];
			else w = d[t.u] + 1;
			if (w < d[ed[s].to]) {
				d[ed[s].to] = w;
				q.push(***(ed[s].to, ed[s].len, w));
			}
		}
	}
	return -1;
}
int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		init();
		while (m--) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}
		printf("%d\n", spfa());
	}
}