code

 #include<bits/stdc++.h>
using namespace std;
//const int mod = 10000007;
const long long inf = 1e15;
//const double Pi = acos(-1.0);
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define rep(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define lc cout<<"\n"
#define print2d(dp,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++)cerr<<dp[i][j]<<" ";cerr<<"\n";}

vector<vector<pair<ll,ll>>> adj1,adj2;

struct edge{
	ll a,b,cost;
};

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	int tt=1;
	//cin>>tt;
	while(tt--){

		int n,m;
		cin>>n>>m;
		adj1.resize(n+1);adj2.resize(n+1);
		vector<edge> ed(m);

		rep(i,0,m){
			ll x,y,w;
			cin>>x>>y>>w;
			adj1[x].pb(mp(y,w));
			adj2[y].pb(mp(x,w));
			ed[i].a=x;ed[i].b=y;ed[i].cost = w;
		}

		vector<ll> d1(n+1,inf),d2(n+1,inf);
		d1[1]=0;d2[n]=0;

		using pll = pair<ll,ll>;

		priority_queue<pll,vector<pll>,greater<pll>> q;
		q.push(mp(0,1));
		while(!q.empty()){
			int v = q.top().S;
			int d_v = q.top().F;
			q.pop();
			if(d_v != d1[v]) continue;
			for (auto e : adj1[v]) {
            	int to = e.first;
            	int len = e.second;

            	if (d1[v] + len < d1[to]) {
                	d1[to] = d1[v] + len;
                	q.push({d1[to], to});
            	}
			}
		}

		priority_queue<pll,vector<pll>,greater<pll>> qn;
		qn.push(mp(0,n));
		while(!qn.empty()){
			int v = qn.top().S;
			int d_v = qn.top().F;
			qn.pop();
			if(d_v != d2[v]) continue;
			for (auto e : adj2[v]) {
            	int to = e.first;
            	int len = e.second;

            	if (d2[v] + len < d2[to]) {
                	d2[to] = d2[v] + len;
                	qn.push({d2[to], to});
            	}
			}
		}


		ll ans = inf;
		for(auto e : ed){
			ans = min(ans,d1[e.a]+d2[e.b]+e.cost/2);
		}
		cout<<ans;
	}
}