/*
cat <<EOF >mistaken-paste
*/

#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

#define BIG 2000000007
#define VERYBIG 200000000000007LL

#define MOD 1000000007
typedef uint64_t ull;
typedef  int64_t sll;

#define N_MAX 200000
#define M_MAX 200000

#include <queue>
#include <stack>
// #include <tuple>
#include <set>
#include <map>

// using namespace std; // HELL
using std::queue;
using std::priority_queue;
using std::stack;
// using std::tuple;
using std::set;
using std::map;
using std::vector;
using std::greater;
using std::pair;

typedef struct {
	int32_t a;
	int32_t b;
} hw;

typedef struct {
	sll a;
	sll b;
} hwll;

typedef struct {
	hwll a;
	hwll b;
} linell;


typedef struct {
	ull s;
	ull t;
	int32_t c;
} struct_a;

typedef struct {
	int32_t from;
	int32_t to;
	sll cost;
} struct_b;

ull n, m;
ull h, w;
ull k;
ull q;
ull vua, vub, vuc, vud, vue, vuf;
sll vsa, vsb, vsc, vsd, vse, vsf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
size_t slen;
size_t tlen;
char ch, dh;

sll c[M_MAX];

hwll arr[M_MAX];

ull solve () {
	sll i, j, ki;
	// ull result = 0;
	sll result = 0;
	// double result = 0;
	ull maybe = 0;
	// sll maybe = 0;
	ull sum = 0;
	// sll sum = 0;
	ull item;
	ull *dpcell;

	typedef pair<ull, ull> v;
	typedef pair<v, sll> distcell;
	map<v, sll> dist;

	typedef pair<sll, v> p;
	typedef pair<v, vector<p> > inserter;
	map<v, vector<p> > g;

	for (i = 0; i < n; i++) {
		dist.insert(distcell(v(i, 0), VERYBIG));
		g.insert(inserter(v(i, 0), {}));
	}
	for (i = 0; i < m; i++) {

		const v va = v(arr[i].a, c[i]);
		const v vb = v(arr[i].b, c[i]);
		const v va0 = v(arr[i].a, 0);
		const v vb0 = v(arr[i].b, 0);

		dist.insert(distcell(va, VERYBIG));
		dist.insert(distcell(vb, VERYBIG));

		if (g.find(va) == g.end()) g.insert(inserter(va, {}));
		if (g.find(vb) == g.end()) g.insert(inserter(vb, {}));

		(*g.find(va)).second.push_back(p(0, vb));
		(*g.find(va)).second.push_back(p(0, va0));
		(*g.find(va0)).second.push_back(p(1, va));

		(*g.find(vb)).second.push_back(p(0, va));
		(*g.find(vb)).second.push_back(p(0, vb0));
		(*g.find(vb0)).second.push_back(p(1, vb));
	}

	(*dist.find(v(0, 0))).second = 0;

	priority_queue<p, vector<p>, greater<p> > q;
	q.push(p(0, v(0, 0)));

	while (!q.empty()) {
		p pdata = q.top();
		q.pop();

		sll currd = pdata.first;
		v currv = pdata.second;

		if ((*dist.find(currv)).second < currd) continue;

		vector<p> arr = (*g.find(currv)).second;
		for (p rail : arr) {
			sll nextd = currd + rail.first;
			v nextv = rail.second;
			if (nextd < (*dist.find(nextv)).second) {
				(*dist.find(nextv)).second = nextd;
				q.push(p(nextd, nextv));
			}
		}
	}

	result = (*dist.find(v(n - 1, 0))).second;
	if (result == VERYBIG) goto fail;

	printf("%llu\n", result);

	return 0;

	fail:
	puts("-1");
	return 1;
}

int32_t main (void) {
	int32_t i, j;
	int32_t x, y;

	scanf("%llu%llu", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%llu", &arr[i].a);
		scanf("%llu", &arr[i].b);
		scanf("%llu", &c[i]);
		arr[i].a--;
		arr[i].b--;
	}

	solve();

	return 0;
}


Measured memory_bytes: 120496