#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <unordered_map>

#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

class Info {
public:
    int dist;
    int node;
    int last;
    int prev;
    Info() {}
    Info(int dist, int node, int last, int prev) {
	this->dist = dist;
	this->node = node;
	this->last = last;
	this->prev = prev;
    }
    bool operator< (const Info &a) const {
	return dist > a.dist;
    }
};

class Edge {
public:
    int next;
    int color;
    Edge() {}
    Edge(int next, int color) {
	this->next = next;
	this->color = color;
    }
    bool operator< (const Edge &a) const {
	return color < a.color;
    }
};

vector<vector<Edge>> nexts;

signed main() {
    int n, m;
    cin >> n >> m;

    nexts.resize(n);

    rep(i, m) {
	int p, q, c;
	cin >> p >> q >> c;
	p--; q--;
	
	nexts[p].push_back(Edge(q, c));
	nexts[q].push_back(Edge(p, c));
    }
    rep(i, n) {
	sort(all(nexts[i]));
    }

    unordered_map<long long, int> minDist;
    minDist[0] = 0;

    priority_queue<Info> q;
    q.push(Info(0, 0, 0, -1));
    while (!q.empty()) {
	Info info = q.top(); q.pop();
	if (info.node == n - 1) {
	    cout << info.dist << endl;
	    return 0;
	}
	long long pr = ((long long)info.node << 30) | info.last;
	if (info.dist > minDist[pr]) continue;
	if (info.last == 0) {
	    for (auto it = nexts[info.node].begin(); it != nexts[info.node].end(); it++) {
		if (info.prev == (*it).next) continue;
		int ndist = info.dist + 1;
		long long pr2 = ((long long)(*it).next << 30) | (*it).color;
		auto it2 = minDist.find(pr2);
		if (it2 != minDist.end() && ndist >= (*it2).second) continue;
		q.push(Info(ndist, (*it).next, (*it).color, info.node));
		if (it2 != minDist.end()) {
		    (*it2).second = ndist;
		} else {
		    minDist.insert(make_pair(pr2, ndist));
		}
	    }
	} else {
	    for (auto it = lower_bound(all(nexts[info.node]), Edge(0, info.last)); it != nexts[info.node].end(); it++) {
		if (info.last != (*it).color) break;
		if (info.prev == (*it).next) continue;
		int ndist = info.dist;
		long long pr2 = ((long long)(*it).next << 30) | (*it).color;
		auto it2 = minDist.find(pr2);
		if (it2 != minDist.end() && ndist >= (*it2).second) continue;
		q.push(Info(ndist, (*it).next, (*it).color, info.node));
		if (it2 != minDist.end()) {
		    (*it2).second = ndist;
		} else {
		    minDist.insert(make_pair(pr2, ndist));
		}
	    }
	    int ndist = info.dist;
	    long long pr2 = ((long long)info.node << 30);
	    auto it2 = minDist.find(pr2);
	    if (it2 != minDist.end() && ndist >= (*it2).second) continue;
	    q.push(Info(ndist, info.node, 0, -1));
	    if (it2 != minDist.end()) {
		(*it2).second = ndist;
	    } else {
		minDist.insert(make_pair(pr2, ndist));
	    }
	}
    }

    cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 25440