tmp.cpp

//dhruv
#include<bits/stdc++.h>
using namespace std;
 
// #define int long long
#define ll long long
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define fro(i,j,n) for(int i = (j);i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define ff first
#define ss second
const int mod = 1e9 + 7;
 
template<typename T>
T binpow(T a,T b,T mod){
	T res = 1;
	while(b){
		if(b&1){
			res = (res*a)%mod;
		}
		b /= 2;
		(a *= a) %= mod;
	}
	return res;
}
 
 
template<typename T>
T binpow(T a,T b){
	T res = 1;
	while(b){
		if(b&1){
			res = (res*a);
		}
		b /= 2;
		a *= a;
	}
	return res;
}
 
template<typename T>
T add(T a,T b){
	return (a + b)%mod;
}
template<typename T>
T sub(T a,T b){
	return add(a,mod - b);
}
template<typename T>
T mul(T a,T b){
	return (a*b)%mod;
}

int make_int(string s){
	int x = 0;
	reverse(s.begin(),s.end());
	string tmp = s;
	for(int i = 0;i < s.length(); ++i){
		x *= 10;
		x += (int)(tmp.back() - '0');
		tmp.pop_back();
	}
	return x;
}
 
string make_string(int s){
	string x;
	while(s){
		x.push_back(char(s%10 + '0'));
		s /= 10;
	}
	reverse(x.begin(),x.end());
	return x;
}


const ll inf = 1e18;
const int mxn = 1e5 + 10;
const int mxm = 2e5 + 10;
int n,m;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq,pq2;


vector<pair<int,int>> adj[mxn],adj2[mxn];
void diks(ll dist[]){
	pq.push({0,0});
	while(!pq.empty()){
		auto tp = pq.top();
		int from = tp.ff;
		ll dst = tp.ss;
		pq.pop();
		if(dist[from] < dst) continue;
		for(auto x : adj[from]){
			int to = x.ff;
			ll cst = x.ss;
			if(dist[from] + cst < dist[to]){
				pq.push({to,dist[from] + cst});
				dist[to] = dist[from] + cst;
			}
		}
	}
}	

void diks2(ll dist2[]){
	pq2.push({n - 1,0});
	while(!pq2.empty()){
		auto tp = pq2.top();
		int from = tp.ff;
		ll dst = tp.ss;
		pq2.pop();
		if(dist2[from] < dst) continue;
		for(auto x : adj2[from]){
			int to = x.ff;
			ll cst = x.ss;
			if(dist2[from] + cst < dist2[to]){
				pq2.push({to,dist2[from] + cst});
				dist2[to] = dist2[from] + cst;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	vector<pair<pair<int,int>,int>> edge(m);
	ll dist[n],dist2[n];
	ffor(i,n){
		dist[i] = inf;
		dist2[i] = inf;
	}
	ffor(i,m){
		int x,y,z;
		cin >> x >> y >> z;
		--x,--y;
		adj[x].push_back({y,z});
		adj2[y].push_back({x,z});
		edge[i] = {{x,y},z};
	}
	dist[0] = 0;
	dist2[n - 1] = 0;
	diks(dist);
	diks2(dist2);
	ll r = dist[n - 1];
	// cout << dist[n - 1];	
	ffor(i,m){
		int x = edge[i].ff.ff;
		int y = edge[i].ff.ss;
		int z = edge[i].ss;
		r = min(dist[x] + dist2[y] + z/2,r);
	}
	cout << r;
	return 0;
}