#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct State {
    long long d;
    int u, used;
    bool operator>(const State& other) const {
        return d > other.d;
    }
};

long long dist[100005][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    for (int i = 1; i <= n; i++) {
        dist[i][0] = INF;
        dist[i][1] = INF;
    }
    priority_queue<State, vector<State>, greater<State>> pq;
    dist[1][0] = 0;
    pq.push({0, 1, 0});
    while (!pq.empty()) {
        auto [d, u, used] = pq.top();
        pq.pop();
        if (d > dist[u][used]) continue;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            long long w = edge.second;
            // Option 1: Don't discount this edge
            if (dist[u][used] + w < dist[v][used]) {
                dist[v][used] = dist[u][used] + w;
                pq.push({dist[v][used], v, used});
            }
            // Option 2: Discount this edge (only if not used yet)
            if (used == 0) {
                long long disc_w = w / 2;
                if (dist[u][0] + disc_w < dist[v][1]) {
                    dist[v][1] = dist[u][0] + disc_w;
                    pq.push({dist[v][1], v, 1});
                }
            }
        }
    }
    long long ans = min(dist[n][0], dist[n][1]);
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}