//#define _GLIBCXX_DEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

#define mk make_pair
#define inb push_back
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define sqr(x) (x) * (x)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define y1 AYDARBOG
//continue break pop_back return

int solve();

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
#define TASK "hamilton-cycle"
#ifndef _DEBUG
    //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
#endif
    solve();
#ifdef _DEBUG
    fprintf(stderr, "\nTIME: %.3f\n", TIME);
#endif
}

const int BUFSZ = (int)1e6 + 7;
char buf[BUFSZ];
string get_str()
{
    scanf(" %s", buf);
    return string(buf);
}

typedef pair<pii, int> edge;
const int INF = 1000000000;
const int MID = 1000000;

int solve()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<pii>> g(n);
    for (int i = 0; i < m; ++i)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        --x, --y;
        g[x].inb(mk(y, c));
        g[y].inb(mk(x, c));
    }
    vector<vi> d(n, vi(2, INF));
    d[0][0] = 0;
    set<pair<int, pii>> q;
    q.insert(mk(0, mk(0, 0)));
    while (!q.empty())
    {
        int u = q.begin()->Y.X;
        int mod = q.begin()->Y.Y;
        int dst = q.begin()->X;
        q.erase(*q.begin());
        for (pii eto : g[u])
        {
            int to = eto.X;
            int t = eto.Y;
            if (dst >= t)
            {
                if (d[to][mod ^ 1] > dst + 1)
                {
                    q.erase(mk(d[to][mod ^ 1], mk(to, mod ^ 1)));
                    d[to][mod ^ 1] = dst + 1;
                    q.insert(mk(d[to][mod ^ 1], mk(to, mod ^ 1)));
                }
            }
            else
            {
                int w = t - dst;
                int f = w & 1;
                int f1 = dst & 1;
                if (f != f1)
                    ++w;
                if (d[to][mod ^ 1] > dst + w + 1)
                {
                    q.erase(mk(d[to][mod ^ 1], mk(to, mod ^ 1)));
                    d[to][mod ^ 1] = dst + w + 1;
                    q.insert(mk(d[to][mod ^ 1], mk(to, mod ^ 1)));
                }
            }
        }
    }
    /*for (int i = 0; i < n; ++i)
    {
        printf("%d %d\n", d[i][0], d[i][1]);
    }*/
    int ans = min(d[n - 1][0], d[n - 1][1]);
    if (ans == INF)
        puts("-1"), exit(0);
    printf("%d\n", ans);
    return 0;
}