#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define pli pair<ll, int>

const ll INF = 1e12;

void dijkstra(int s, vector<vector<pii>> &graf, vector<ll> &tav, vector<int> &honnan) {
    priority_queue<pli, vector<pli>, greater<pli>> q;
    q.push({0, s});
    tav[s] = 0;
    while(!q.empty()) {
        int index = q.top().second;
        ll d = q.top().first;
        q.pop();
        if(d != tav[index]) continue;
        for(pii el : graf[index]) {
            int cel = el.first;
            int w = el.second;
            if(tav[index] + w < tav[cel]) {
                tav[cel] = tav[index] + w;
                q.push({tav[cel], cel});
                honnan[cel] = index;
            }
        }
    }
}

int main() {
	int n, m;
    cin >> n >> m;
    vector<vector<pii>> graf(n);
    vector<ll> a(n, INF), b(n, INF);
    vector<int> honnan(n, -1);
    for(int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        graf[x].push_back({y, w});
        graf[y].push_back({x, w});
    }
    dijkstra(0, graf, a, honnan);
    dijkstra(n - 1, graf, b, honnan);
    vector<bool> ut(n);
    int most = 0;
    while(most != n - 1) {
        ut[most] = true;
        most = honnan[most];
    }
    ut[n - 1] = true;
    //for(int i = 0; i < n; i++) if(ut[i]) cout << i << " ";
    //cout << endl;
    //cout << b[1] << " " << a[2] << endl;
    unsigned int eredmeny = -1;
    for(int i = 0; i < n; i++) {
        for(pii el : graf[i]) {
            int index = el.first;
            int w = el.second;
            int kell = b[0] - a[i] - b[index] - 1;
            if((!ut[i] || !ut[index]) && kell < w && kell > 0) eredmeny = min(eredmeny, (unsigned int)(w - kell));
            kell = b[0] - b[index] - a[i] - 1;
            if((!ut[i] || !ut[index]) && kell < w && kell > 0) eredmeny = min(eredmeny, (unsigned int)(w - kell));
            //cout << i << " " << index << " " << kell << endl;
        }
    }
    cout << (int)eredmeny << endl;
}