#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<62);
struct Edge { int u,v; long long w; int idx; };
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
if(!(cin >> N >> M)) return 0;
vector<Edge> edges;
edges.reserve(M);
vector<vector<pair<int,long long>>> g(N+1);
for(int i=1;i<=M;i++){
int a,b; long long w;
cin >> a >> b >> w;
edges.push_back({a,b,w,i});
g[a].push_back({b,w});
g[b].push_back({a,w});
}
auto dijkstra = [&](int src){
vector<long long> dist(N+1, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
dist[src]=0;
pq.push({0,src});
while(!pq.empty()){
auto [d,u]=pq.top(); pq.pop();
if(d!=dist[u]) continue;
for(auto &e: g[u]){
int v=e.first; long long w=e.second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
};
auto dist1 = dijkstra(1);
auto distN = dijkstra(N);
long long orig = dist1[N];
// If orig is INF, graph disconnected (but problem guarantees connected)
// Prepare suffix maximum P_i by original order 1..M
vector<long long> P(M+2, 0);
// map index->W
vector<long long> W(M+1);
for(auto &e: edges) W[e.idx] = e.w;
for(int i=M;i>=1;i--){
P[i] = max(P[i+1], W[i]);
}
long long ans = orig;
for(auto &e: edges){
int i = e.idx;
long long add = P[i+1]; // largest W_j with j>i
if(add==0) continue; // no larger-index edge to replicate
// two possible orientations
long long cand1 = INF, cand2 = INF;
if(dist1[e.u]!=INF && distN[e.v]!=INF){
cand1 = dist1[e.u] + e.w + add + distN[e.v];
}
if(dist1[e.v]!=INF && distN[e.u]!=INF){
cand2 = dist1[e.v] + e.w + add + distN[e.u];
}
long long cand = min(orig, min(cand1, cand2));
// We want the shortest path length after performing this extension.
// Using min(orig, ...) is safe because other routes might remain orig.
if(cand>ans) ans=cand;
}
cout << ans << "\n";
return 0;
}
