//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;
}
