#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define Unique(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());
const int N = 3e5 + 5;
int n, m;
int w[N], p[N];
vector<pii> adj[N];
ll d1[N], dn[N];
void Dijkstra(int s, ll dist[]) {
priority_queue<pll, vector<pll>, greater<pll>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, id] : adj[u]) {
if (dist[v] > d + w[id]) {
dist[v] = d + w[id];
pq.push({dist[v], v});
}
}
}
}
int par[N];
int findSet(int u) {
return (u == par[u] ? u : par[u] = findSet(par[u]));
}
void UnionSet(int u, int v) {
u = findSet(u);
v = findSet(v);
par[u] = v;
}
vector<pii> g[N];
bool mark[N];
int id;
int low[N], num[N];
bool Dfs(int u, int p_id, ll len) {
num[u] = low[u] = ++id;
for (auto [v, i] : g[u]) {
if (i == p_id) continue;
if (!num[v]) {
if (Dfs(v, i, len)) return true;
low[u] = min(low[u], low[v]);
if (low[v] == num[v]) {
if (d1[u] + w[i] + p[i] + dn[v] > len &&
d1[v] + w[i] + p[i] + dn[u] > len)
return true;
}
}
else low[u] = min(low[u], num[v]);
}
return false;
}
bool check(ll len) {
for (int i = 1; i <= n; i++) {
par[i] = i;
g[i].clear();
low[i] = num[i] = 0;
}
for (int i = 1; i <= m; i++)
mark[i] = false;
for (int u = 1; u <= n; u++) {
for (auto [v, i] : adj[u]) {
if (!mark[i] && (d1[u] + w[i] + dn[v] <= len || d1[v] + w[i] + dn[u] <= len)) {
mark[i] = true;
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
UnionSet(u, v);
}
}
}
if (findSet(1) != findSet(n)) return false;
id = 0; return Dfs(1, -1, len);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "beautiful"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
cin>>n>>m;
for (int i = 1; i <= m; i++) {
int u, v; cin>>u>>v>>w[i];
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
for (int i = m; i >= 1; i--)
p[i] = max(p[i + 1], w[i + 1]);
memset(d1, 0x3f, sizeof d1); Dijkstra(1, d1);
memset(dn, 0x3f, sizeof dn); Dijkstra(n, dn);
ll l = d1[n];
ll r = l + p[1];
ll ans = d1[n] - 1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
cout<<ans + 1;
cerr<<setprecision(3)<<fixed<<"Time elapsed: "<< 1.0 * clock() / CLOCKS_PER_SEC <<"s\n";
}
