Flight_Discount_CSES

//PPAP_1264589
#include "bits/stdc++.h"
#define Task "A"
#define up(i,a,b) for (int i = a; i <= b; i++)
#define pii pair<int, long long>
#define plli pair<long long, int>
#define f first
#define s second
#define ep emplace_back
using namespace std;

const int maxn = 1e5 + 10;
int n,m;
vector<pii> a[maxn];
vector<pii> b[maxn];
struct edge{
    int u,v;
    long long w;
};
vector<edge> E;

void in(){
    cin >> n >> m;
    int u,v;
    long long w;
    up(i,1,m){
        cin >> u >> v >> w;
        a[u].ep(v, w);
        b[v].ep(u, w);
        E.push_back({u, v, w});
    }
}

namespace Solution1{
    priority_queue<plli, vector<plli>, greater<plli>> P;
    long long d1[maxn], dn[maxn];

    void minimalize(const long long curw, pii x, long long d[]){
        int v = x.f;
        long long w = x.s;
        if (d[v] > curw + w){
            d[v] = curw + w;
            P.push({d[v], v});
        }
    }

    void Dijkstra(int root, long long d[]){
        fill(d+1, d+n+1, 1e18 + 31);
        d[root] = 0;
        P.push({0, root});
        while (!P.empty()){
            int u = P.top().s;
            long long curw = P.top().f;
            P.pop();
            if (curw > d[u]) continue;
            if (root == 1) for (pii x : a[u]){
                minimalize(curw, x, d);
            }
            if (root == n) for (pii x : b[u]){
                minimalize(curw, x, d);
            }
        }
    }

    long long check_edges(){
        long long res = 1e18 + 31;
        for (auto e : E){
            int u = e.u;
            int v = e.v;
            long long w = e.w;
            long long newval = d1[u] + dn[v] + w/2;
            if (res > newval) res = newval;
        }
        return res;
    }

    void MAIN(){
        in();
        Dijkstra(1, d1);
        Dijkstra(n, dn);
        cout << check_edges();
    }
}

namespace Solution2{
    struct NODE{
        long long val;
        int nod;
        bool used;
    };
    inline bool operator < (const NODE& x, const NODE& y){
        return x.val > y.val;
    }   priority_queue<NODE> P;

    long long d[2][maxn];

    void minimalize(long long curw, pii x, bool curused){
        int v = x.f;
        long long w = x.s;
        long long newval;

        newval = curw + w;
        if (d[curused][v] > newval){
            d[curused][v] = newval;
            P.push({newval, v, curused});
        }

        if (!curused){
            newval = curw + w/2;
            if (d[1][v] > newval){
                d[1][v] = newval;
                P.push({newval, v, 1});
            }
        }
    }

    void Dijkstra(){
        fill(d[0]+1, d[0]+n+1, 1e18 + 31);
        fill(d[1]+1, d[1]+n+1, 1e18 + 31);
        d[0][1] = 0;
        d[1][1] = 0;
        P.push({0, 1, 0});
        while (!P.empty()){
            int u = P.top().nod;
            long long curw = P.top().val;
            bool curused = P.top().used;
            P.pop();
            if (curw > d[curused][u]) continue;
            for (pii x : a[u]){
                minimalize(curw, x, curused);
            }
        }
    }

    void MAIN(){
        in();
        Dijkstra();
        cout << d[1][n];
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //Solution1::MAIN();
    Solution2::MAIN();
}

// Algorithmic logic