#include <bits/stdc++.h>
using namespace std;
//variable
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
//vector
#define pb push_back
#define all(v) v.begin(),v.end()
#define len(a) (int)a.length()
#define sz(a) (int)a.size()
//mask
#define BIT(i) (1LL<<(i))
//better code, debugger
#define watch(n) cerr << #n << ": " << n << endl
#define debug(x) for (auto p: x) cerr<<p<<' ';cerr<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define fIlE "test."
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//mt19937 RAND(seed);
const int mod = 1e9 + 7;
inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
inline int mul(int u,int v){return (ll)u*v%mod;}
#define tt pair<ll, int>
const ll inf = 1e16;
int n, m;
vector<ii> a[100000 + 100];
vector<ii> g[100000 + 100];
ll dist1[100000 + 100];
ll distn[100000 + 100];
void solve()
{
    cin >> n >> m;
    while(m--){
        int u, v, d;
        cin >> u >> v >> d;
        a[u].pb(mp(v, d));
        g[v].pb(mp(u, d));
    }
    priority_queue<tt, vector<tt>, greater<tt> > haha;
    forw(i, 1, n)
        dist1[i] = inf;
    haha.push(mp(dist1[1] = 0, 1));
    while(!haha.empty())
    {
        int u; ll d;
        u = haha.top().s, d = haha.top().f;
        haha.pop();
        if (dist1[u] < d) continue;
        for (auto [v, e] : a[u])
        {
            if (dist1[v] > e + d)
            {
                dist1[v] = e + d;
                haha.push(mp(dist1[v], v));
            }
        }
    }
    priority_queue<tt, vector<tt>, greater<tt> > haha2;
    forw(i, 1, n)
        distn[i] = inf;
    haha2.push(mp(distn[n] = 0, n));
    while(!haha2.empty())
    {
        int u; ll d;
        u = haha2.top().s, d = haha2.top().f;
        haha2.pop();
        if (distn[u] < d) continue;
        for (auto [v, e] : g[u])
        {
            if (distn[v] > e + d)
            {
                distn[v] = e + d;
                haha2.push(mp(distn[v], v));
            }
        }
    }
    ll ans = inf;
    forw(u, 1, n) for (auto [v, e] : a[u])
        ans = min(ans, dist1[u] + distn[v] + e / 2);
    cout << ans;

}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(fIlE"inp", "r"))
        freopen(fIlE"inp","r",stdin);
    if (fopen(fIlE"out", "r"))
        freopen(fIlE"out","w",stdout);
    //time_t TIME_TU=clock();
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}