#include <array>
#include <climits>
#include <iostream>
#include <optional>
#include <queue>
#include <set>
#include <vector>

using namespace std;

using ll = long long;

ll const INF = LLONG_MAX / 3;

pair<vector<int>, vector<ll>> dijkstra(
    vector<vector<pair<int, ll>>> const& graph,
    int const start
) {
    vector<ll> dist(graph.size(), INF);
    vector<int> from(graph.size(), -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    dist[start] = 0;
    pq.push({ 0, start });

    while (!pq.empty()) {
        auto [cur_dist, cur] = pq.top();
        pq.pop();

        if (cur_dist != dist[cur])
            continue;

        for (auto const& [neigh, w] : graph[cur]) {
            ll const new_dist = cur_dist + w;

            if (new_dist >= dist[neigh])
                continue;

            dist[neigh] = new_dist;
            from[neigh] = cur;
            pq.push({ new_dist, neigh });
        }
    }

    return { from, dist };
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, ll>>> graph(n);
    vector<tuple<int, int, ll>> edges(m);

    for (auto& [u, v, w] : edges) {
        cin >> u >> v >> w;
        
        graph[u].push_back({ v, w });
        graph[v].push_back({ u, w });
    }

    auto const [shortest_from, shortest_dist] = dijkstra(graph, 0);
    ll const base_dist = shortest_dist[n - 1];

    vector<bool> bad_cities(n, false);
    {
        int cur = n - 1;
        bad_cities[cur] = true;;

        while (shortest_from[cur] != -1) {
            cur = shortest_from[cur];
            bad_cities[cur] = true;
        }
    }

    auto const [_a, dist_a] = dijkstra(graph, 0);
    auto const [_b, dist_b] = dijkstra(graph, n - 1);

    ll ans = INF;

    for (auto const& [u, v, w] : edges) {
        if (bad_cities[u] && bad_cities[v])
            continue;

        for (auto const& [x, y] : vector<pair<int, int>>{ { u, v }, { v, u } }) {
            ll new_w = base_dist - 1 - dist_a[x] - dist_b[y];

            if (new_w < 1)
                continue;

            ll const cost = w - new_w;

            ans = min(ans, cost);
        }
    }

    if (ans == INF)
        cout << "-1\n";
    else
        cout << ans << "\n";
}