#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <limits.h>

using namespace std;

int main()
{
    int n, m, i, j, temp1, temp2;
    cin >> n >> m;

    vector<vector<int>> edgematrix(n, vector<int>(n, -1));
    vector<vector<bool>> inoptpath(n, vector<bool>(n, 0));
    vector<vector<int>> last(2, vector<int>(n));
    last[0][0] = -1, last[1][n-1] = -1;

    vector<vector<pair<int, int>>> connections(n);

    for (i = 0; i < m; i++)
    {
        cin >> temp1 >> temp2;

        cin >> edgematrix[temp1][temp2];
        edgematrix[temp2][temp1] = edgematrix[temp1][temp2];

        connections[temp1].push_back({ temp2, edgematrix[temp1][temp2] });
        connections[temp2].push_back({ temp1, edgematrix[temp1][temp2] });
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> steps;

    vector<vector<int>> distance(2, vector<int>(n, INT_MAX));
    distance[0][0] = 0, distance[1][n-1] = 0;

    int starts[2] = { 0, n - 1 };

    for (i = 0; i < 2; i++)
    {
        steps.push({ 0, starts[i] });

        while (steps.size() > 0)
        {
            for (j = 0; j < connections[steps.top().second].size(); j++)
            {
                if (distance[i][connections[steps.top().second][j].first] > steps.top().first + connections[steps.top().second][j].second)
                {
                    distance[i][connections[steps.top().second][j].first] = (steps.top().first + connections[steps.top().second][j].second);
                    steps.push({steps.top().first + connections[steps.top().second][j].second, connections[steps.top().second][j].first});
    
                    last[i][connections[steps.top().second][j].first] = steps.top().second;
                }
            }
            steps.pop();
        }
    }

    temp1 = n - 1;

    while (last[0][temp1] != -1)
    {
        inoptpath[temp1][last[0][temp1]] = true, inoptpath[last[0][temp1]][temp1] = true;
        temp1 = last[0][temp1];
    }

    int opt = distance[0][n - 1];
    int min, mini;
    set<int> nope;

    while (true)
    {
        min = INT_MAX;

        for (i = 1; i < n-1; i++)
        {
            if (min > distance[0][i] + distance[1][i] && distance[0][i] + distance[1][i] != opt && !nope.count(i))
            {
                min = distance[0][i] + distance[1][i];
                mini = i;
            }
        }

        if (min == INT_MAX)
        {
            cout << -1;
            return 0;
        }
        
        int maxreduction = 0;

        for (i = 0; i < 2; i++)
        {
            temp1 = mini;

            while (last[i][temp1] != -1)
            {
                if (inoptpath[temp1][last[i][temp1]])
                {
                    temp1 = last[i][temp1];
                    continue;
                }

                if (maxreduction < edgematrix[temp1][last[i][temp1]] - 1)
                {
                    maxreduction = edgematrix[temp1][last[i][temp1]] - 1;
                    if (maxreduction > distance[0][mini] + distance[1][mini] - opt)
                    {
                        cout << distance[0][mini] + distance[1][mini] - opt + 1;
                        return 0;
                    }
                }

                temp1 = last[i][temp1];
            }
        }

        nope.insert(mini);
    }
}
//10 13
//0 1 60
//0 2 20
//1 2 5
//1 3 6
//1 4 8
//2 5 20
//3 6 36
//4 7 12
//5 7 20
//5 8 20
//6 9 40
//7 9 20
//8 9 35