Untitled

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lld;
#define pll pair<ll,ll>
#define vll vector<ll>
#define  ln "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define be begin
#define ub upper_bound
#define lb lower_bound
#define bi binary_search
#define sll set <ll>
#define msll multiset <ll>
#define vpll vector <pair<ll,ll>>
#define mll  map <ll,ll>
#define all(v) v.begin(),v.end()
#define mem1(a)  memset(a,-1,sizeof(a))
#define mem0(a)  memset(a,0,sizeof(a))
#define i1(x) cin>>x
#define i2(x1,x2) cin>>x1>>x2
#define i3(x1,x2,x3) cin>>x1>>x2>>x3
#define i4(x1,x2,x3,x4) cin>>x1>>x2>>x3>>x4
#define o1(x) cout<<x<<ln
#define o2(x1,x2) cout<<x1<<" "<<x2<<ln
#define o3(x1,x2,x3) cout<<x1<<" "<<x2<<" "<<x3<<ln
#define o4(x1,x2,x3,x4) cout<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<ln
#define rep(i,s,e) for(ll i=s;i<e;i++)
#define rrep(i,s,e) for(ll i=s-1;i>=e;i--)
#define geta(a,n) for(ll i=0;i<n;i++)cin>>a[i];
const ll mod = 1e9 + 7;
vector <pll> adj[200100];
vector <vll>  dis(200100, vll(2, 1e18));
vll vis(200100, 0);
void solve()
{
	ll n, m;
	i2(n, m);
	rep(i, 0, m)
	{
		ll k1, k2, k3;
		i3(k1, k2, k3);
		adj[k1].push_back({k2, k3});
 
	}
	set <pair <ll, pll>> pq;
	dis[1][0] = 0;
	pq.insert({0, {1, 0}});
	while (!pq.empty())
	{
		pair <ll, pll> p = *(pq.begin());
		pq.erase(pq.begin());
		ll y = p.first;
		ll x = p.second.first;
		// if (vis[x]==1)
		// 	continue;
		// vis[x]++;
		//o3(p.first, p.second.first, p.second.second);
		//o2(x,y);
		for (auto i : adj[x])
		{
			//o3(dis[i.first],dis[x],i.second);
			if (p.second.second == 0)
			{	
				if (dis[i.first][0] > dis[x][0] + i.second)
				{
					pq.erase({ dis[i.first][0], {i.first, p.second.second}});
					dis[i.first][0] = dis[x][0] + i.second;
					//o2(i.first,dis[i.first]);
					pq.insert({ dis[i.first][0], {i.first, p.second.second}});
				}
			}
			else
			{
				if (dis[i.first][1] > dis[x][1] + i.second)
				{
					pq.erase({ dis[i.first][1], {i.first, p.second.second}});
					dis[i.first][1] = dis[x][1] + i.second;
					//o2(i.first,dis[i.first]);
					pq.insert({ dis[i.first][1], {i.first, p.second.second}});
				}
			}
 
			if (p.second.second == 0)
			{
				if (dis[i.first][1] > dis[x][0] + i.second / 2)
				{
					pq.erase({dis[i.first][1], {i.first, 1}});
					dis[i.first][1] = dis[x][0] + i.second / 2;
					//o2(i.first,dis[i.first]);
					pq.insert({dis[i.first][1], {i.first, 1}});
				}
			}
		}
	}
	o1(dis[n][1]);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t = 1;
	//cin >> t;
 
	srand(time(0));
	for (ll i = 1; i <= t; i++)
	{
 
		//cout << "Case #" << i << ": ";
 
		solve();
 
	}
	return 0;
}