#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int MAXN = 3e5 + 25;
vector <array <ll, 3>> adj[MAXN];
array <ll, 4> edges[MAXN];
int n, m;
ll dist[2][MAXN];
void dijkstra (int c, int node) {
for (int i = 1; i <= n; i++) {
dist[c][i] = inf;
}
dist[c][node] = 0;
priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq;
pq.push({0, node});
while (!pq.empty()) {
auto k = pq.top();
pq.pop();
if (k.first > dist[c][k.second]) {
continue;
}
for (auto [j, w, e] : adj[k.second]) {
if (w + k.first < dist[c][j]) {
dist[c][j] = w + k.first;
pq.push({dist[c][j], j});
}
}
}
/* cout << node << ": ";
for (int i = 1; i <= n; i++) {
cout << dist[c][i] << " ";
}
cout << '\n';*/
}
vector <pair <int, int>> c[MAXN];
int in[MAXN], out[MAXN], tt, dp[MAXN], vis[MAXN];
int flag;
ll T;
void dfs (int pos, int par) {
in[pos] = ++tt;
dp[pos] = tt;
vis[pos] = 1;
for (auto [j, i] : c[pos]) {
if (j == par) {
continue;
}
if (!vis[j]) {
dfs(j, pos);
dp[pos] = min(dp[pos], dp[j]);
if (dp[j] > in[pos] && vis[n] && in[j] <= in[n] && out[n] <= out[j]) {
int u = 1;
u &= dist[0][pos] + dist[1][j] + edges[i][2] + edges[i][3] > T;
u &= dist[0][j] + dist[1][pos] + edges[i][2] + edges[i][3] > T;
flag |= u;
}
} else {
dp[pos] = min(dp[pos], in[j]);
}
}
out[pos] = tt;
}
bool check (ll t) {
T = t;
for (int i = 1; i <= n; i++) {
c[i].clear(); vis[i] = 0;
in[i] = out[i] = 0;
}
tt = 0; flag = 0;
for (int i = 1; i <= m; i++) {
auto x = edges[i];
if (dist[0][x[0]] + dist[1][x[1]] + x[2] <= t || dist[0][x[1]] + dist[1][x[0]] + x[2] <= t) {
c[x[0]].push_back({x[1], i});
c[x[1]].push_back({x[0], i});
}
}
dfs(1, -1);
return flag;
}
void solve () {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c; cin >> a >> b >> c;
if (a == b) {
m--; i--; continue;
}
edges[i] = {a, b, c, 0};
}
ll mx = 0;
for (int i = m; i >= 1; i--) {
edges[i][3] = mx;
mx = max(mx, edges[i][2]);
}
for (int i = 1; i <= m; i++) {
adj[edges[i][0]].push_back({edges[i][1], edges[i][2], edges[i][3]});
adj[edges[i][1]].push_back({edges[i][0], edges[i][2], edges[i][3]});
}
dijkstra(0, 1);
dijkstra(1, n);
ll l = dist[0][n], r = dist[0][n] + 1e9, ans = dist[0][n] - 1;
while (l <= r) {
ll mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1; ans = mid;
} else {
r = mid - 1;
}
}
cout << ans + 1 << '\n';
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
