Shared code

//Sublime with mod inv and exp

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define _mp make_pair
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
#define _f first
#define _s second
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p._f); cerr << ","; _print(p._s); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#define _d(x) _p(x); cout << endl;
void _p(ll t)     {cout << t;}
void _p(int t)    {cout << t;}
void _p(string t) {cout << t;}
void _p(char t)   {cout << t;}
void _p(lld t)    {cout << t;}
void _p(double t) {cout << t;}
void _p(ull t)    {cout << t;}
template <class T, class V> void _p(pair <T, V> p);
template <class T> void _p(vector <T> v);
template <class T> void _p(set <T> v);
template <class T, class V> void _p(map <T, V> v);
template <class T> void _p(multiset <T> v);
template <class T, class V> void _p(pair <T, V> p) {cout << "{"; _p(p.ff); cout << ","; _p(p.ss); cout << "}";}
template <class T> void _p(vector <T> v) {cout << "[ "; for (T i : v) {_p(i); cout << " ";} cout << "]";}
template <class T> void _p(set <T> v) {cout << "[ "; for (T i : v) {_p(i); cout << " ";} cout << "]";}
template <class T> void _p(multiset <T> v) {cout << "[ "; for (T i : v) {_p(i); cout << " ";} cout << "]";}
template <class T, class V> void _p(map <T, V> v) {cout << "[ "; for (auto i : v) {_p(i); cout << " ";} cout << "]";}
#define _sz(x) ((int)(x).size())
#define _a(x) (x).begin(), (x).end()

#define pb push_back
#define pob pop_back
#define int long long int
#define vvi vector<vector<int>>
#define vi vector<int>
#define _vvb vector<vector<bool>>
#define mnh priority_queue<int, vector<int>, greater<int>>
#define mxh priority_queue<int>
#define _m map<int, int>
#define _um unordered_map<int, int>
#define vs vector<string>
#define _vvs vector<vector<string>>
#define _vc vector<char>
#define _vvc vector<vector<char>>
#define _vpi vector<pair<int, int>
#define pii pair<int, int>
/*-------------------------------------------------------------------------------------------------------------------------*/


int mul(int a, int b) {
    return 1LL * a * b % MOD;
}
int modPow(int b, int p) {
    if (p == 0)
        return 1;

    int x = modPow(b, p / 2);

    return p % 2 == 0 ? mul(x, x) : mul(b, mul(x, x));
}

int moduloInverse(int n) {
    //(p / n) % mod  
    return modPow(n, MOD - 2);
}
int mod_exp(int base, int exp, int mod)
{
    int res = 1;
    base %= mod;
    while (exp > 0)
    {
        if (exp & 1)//if exp is odd
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
/*-------------------------------------------------------------------------*/
vector<int>min_dist(int src, vector<vector<pair<int, int>>>&v, int n, int m)
{
    vector<int>ans(n + 1, INF);
    ans[src] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    pq.push({0, src});
    while(pq.size())
    {
        auto curr_state = pq.top(); pq.pop();
        int nn = curr_state.second;
        debug(nn);
        for(auto &pr : v[nn])
        {
            int ch = pr.first, cost = pr.second;
            debug(ch);
            if(ans[nn] + cost < ans[ch])
            {
                ans[ch] = ans[nn] + cost;
                pq.push({ans[ch], ch});
            }
        }        
    }
    return ans;
}
void solve(){

    int n, m;
    cin>>n>>m;
    
    vector<vector<pair<int, int>>>rev_v(n + 1), v(n + 1);

    for(int o = 0; o < m; o++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        rev_v[b].push_back({a, c});
        v[a].push_back({b, c});
    }

    vector<int>from_start = min_dist(1, v, n, m);
    vector<int>from_end = min_dist(n, rev_v, n, m);
    debug(from_start); debug(from_end);
    int answer = INF;
    for(int a = 1; a <= n; a++)
    {
        for(auto &pr : v[a])
        {
            int b = pr.first, cost = pr.second;
            int curr = from_start[a] + (cost / 2) + from_end[b];
            if(curr < answer) answer = curr;
        }
    }
    cout<<answer<<endl;
  return;
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("error.txt", "w", stderr);    
#endif
fastio();

ll t;
// cin>>t;
t = 1;
while(t--)solve();
return 0;
}