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

const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

const double PI = acos(-1);
using ll= long long;
#define int ll
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

const int INF=4e18;

void solve() {
    cini(n);
    cini(m);

    vector<vector<pii>> adj(n);
    for(int i=0; i<m; i++) {
        cini(a); a--;
        cini(b); b--;
        cini(w);
        adj[a].emplace_back(b,w);
    }

    vvi dp(2, vi(n, INF)); /* dp[0] without using coupon, dp[1] with using coupon */
    dp[0][0]=0;
    dp[1][0]=0;
    priority_queue<pii> q;
    q.emplace(0,0);
    while(q.size() && -q.top().first<max(dp[0][n-1], dp[1][n-1])) {
        int node=q.top().second;
        q.pop();
        for(auto chl : adj[node]) {
            bool pu=false;
            if(dp[0][chl.first]>dp[0][node]+chl.second) {
                dp[0][chl.first]=dp[0][node]+chl.second;
                pu=true;
            }
            if(dp[1][chl.first]>dp[1][node]+chl.second) {
                dp[1][chl.first]=dp[1][node]+chl.second;
                pu=true;
            }
            if(dp[1][chl.first]>dp[0][node]+(chl.second/2)) {
                dp[1][chl.first]=dp[0][node]+(chl.second/2);
                pu=true;
            }
            if(pu)
                q.emplace(-dp[1][chl.first], chl.first);
        }
    }
    cout<<min(dp[1][n-1], dp[0][n-1])<<endl;
}

signed main() {
    solve();
}