#include <bits/stdc++.h>
#define all(x)                x.begin(),x.end()
#define F                     first
#define pb                    push_back
#define S                     second
#define IOfast                ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(x)              cout<<#x<<" = "<<x<<"\n";
#define error(args...)        { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
using namespace std;

vector < pair<int64_t,int> > graph[(int)1e5 + 1];
vector<int64_t> mx((int)1e5+1,0); //max in the path //i am storing max so in case it changes i can edit my distance
vector<int64_t> dist((int)1e5 + 1,LLONG_MAX / 100LL);

void diskstra(int n)
{
  set<pair<int64_t,int>> s = {{0,1}};
  dist[1] = 0;
  mx[1] = 0; //max from one to

  while(s.size())
  {
    int64_t value = (*s.begin()).F;
    int vertex = (*s.begin()).S;
    s.erase(s.begin());

    for(auto child:graph[vertex])
    {
      //vetex -> child
      //creating a new distance by discarding old coupon and creating new discount coupon as child.F > mx[vertex]
      if(child.F > mx[vertex] && dist[child.S] > value + ((mx[vertex]+1)/2) + (child.F/2) )
      {
        s.erase({dist[child.S],child.S});
        dist[child.S] =  value + ((mx[vertex]+1)/2) + (child.F/2);
        s.insert({dist[child.S],child.S});
        mx[child.S] = child.F;
      }
      if(dist[child.S] >= dist[vertex] + child.F)
      {
        s.erase({dist[child.S],child.S});
        //if the distance are same then minimize the maximum in the path
        //so if new edge comes with greater value i can discard old maximum
        // and create new discount coupon with minimum total
        if(dist[child.S] == dist[vertex] + child.F)
          mx[child.S] = min(mx[child.S],mx[vertex]);
        else
          mx[child.S] = mx[vertex];
        dist[child.S] = dist[vertex] + child.F;
        s.insert({dist[child.S],child.S});
      }
    }
  }
  cout<<dist[n];
}

void solve()
{
  int n,m,u,v,cost;
  cin>>n>>m;
  while(m--)
  {
    cin>>u>>v>>cost;
    graph[u].pb({cost,v});
  }
  diskstra(n);
}

int main()
{
  IOfast;
  solve();
  return 0;
}