#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()
using Edge = array<int, 3>;
const int inf = 9e18;
int32_t main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, Wmax = 0; cin >> n >> m;
vector<Edge> edge(m);
for (auto& [u, v, w] : edge) cin >> u >> v >> w, u--, v--, Wmax = max(Wmax, w);
vector<int> P(m, 0);
for (int i = m-2; i > -1; i--) P[i] = max(P[i+1], edge[i+1][2]);
vector<int> S(n), T(n);
vector<vector<pii>> G(n);
for (auto [u, v, w] : edge) G[u].push_back({v, w}), G[v].push_back({u, w});
auto dijkstra = [&](int s, vector<int>& dist){
priority_queue<pii, vector<pii>, greater<pii>> pq;
fill(entire(dist), inf); pq.push(pii{0, s});
while (!pq.empty()){
auto [W, u] = pq.top(); pq.pop();
if (dist[u] != inf) continue;
else dist[u] = W;
for (auto [v, w] : G[u]) pq.push(pii{W + w, v});
}
}; dijkstra(0, S); dijkstra(n-1, T);
auto check = [&](int lim){
vector<vector<Edge>> H(n); // H[u] -> { v, w, i }
for (int i = 0; i < m; i++){
auto [u, v, w] = edge[i];
int dmin = min(S[u] + T[v], S[v] + T[u]) + w;
if (dmin > lim) continue;
H[u].push_back({v, w, i}); H[v].push_back({u, w, i});
}
int timer = 0;
vector<bool> vis(n, false);
vector<int> tin(n), tout(n), ei(n), pi(n);
vector<vector<int>> adj(n);
auto dfs = [&](auto&& self, int s, int parent, int idx) -> void{
if (vis[s]) return;
else vis[s] = true;
ei[s] = idx, pi[s] = parent, tin[s] = timer++;
for (auto [u, w, i] : H[s]) if (!vis[u]) {
adj[s].push_back(u); self(self, u, s, i);
} tout[s] = timer++;
}; dfs(dfs, 0, 0, -1);
vector<bool> bridge(m, false);
vector<pii> dp(n, {inf, -1}); // minT, maxT
auto dfsdp = [&](auto&& self, int s) -> bool{
bool npi = (s == n-1);
for (auto u : adj[s]){
npi |= self(self, u);
dp[s].ff = min(dp[u].ff, dp[s].ff);
dp[s].ss = max(dp[u].ss, dp[s].ss);
} for (auto [u, w, i] : H[s]) if (u != pi[s]){
dp[s].ff = min(dp[s].ff, tin[u]);
dp[s].ss = max(dp[s].ss, tin[u]);
}
if (pi[s] == s) return npi;
if (!(tin[s] <= dp[s].ff and dp[s].ss <= tout[s])) return npi;
else if (npi) bridge[ei[s]] = true;
return npi;
}; dfsdp(dfsdp, 0);
for (int i = 0; i < m; i++) if (bridge[i]){
auto [u, v, w] = edge[i];
int dist = min(S[u] + T[v], S[v] + T[u]) + w + P[i];
if (dist > lim) return true;
}
return false;
};
int low = inf, high;
for (auto [u, v, w] : edge){
low = min(low, min(S[u] + T[v], S[v] + T[u]) + w);
} high = low + Wmax + 1ll; low--;
while (low < high){
int mid = (low + high + 1) / 2;
if (check(mid)) low = mid;
else high = mid-1;
}
cout << low + 1 << endl;
return 0;
}
