#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 3e5 + 10;
const int M = 3e5 + 10;
ve<int> gr[N];
int n;
array<int,3> edges[M];
inline int go(const int &ID, const int &v) { return v ^ edges[ID][0] ^ edges[ID][1]; }
inline ve<ll> dij(const int &s) {
ve<ll> d(n, inf); d[s] = 0;
set<pll> st; st.insert({d[s], s});
while (sz(st)) {
int v = st.begin()->se;
st.erase(st.begin());
for (auto &id : gr[v]) {
int to = go(id, v);
int w = edges[id][2];
if (d[to] > d[v] + w) {
st.erase({d[to], to});
d[to] = d[v] + w;
st.insert({d[to], to});
}
}
}
return d;
}
inline void solve() {
int m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int v, u, w;
cin >> v >> u >> w;
edges[i] = {--v, --u, w};
gr[v].pb(i);
gr[u].pb(i);
}
ve<int> sf(m);
for (int i = m - 2; ~i; --i) {
sf[i] = max(sf[i + 1], edges[i + 1][2]);
}
auto d0 = dij(0);
auto d1 = dij(n - 1);
auto can = [&](const ll &x) -> bool {
ve<bool> useless(m);
ve<bool> bridge(m);
for (int i = 0; i < m; ++i) {
auto &[v, u, w] = edges[i];
ll cost = min(d0[v] + d1[u], d1[v] + d0[u]) + w;
if (cost >= x) useless[i] = 1;
else if (cost + sf[i] >= x) useless[i] = 2;
}
int timer = 0;
ve<int> in(n), up(n), used(n);
function<void(int)> dfs = [&](int v) {
used[v] = 1;
in[v] = up[v] = timer++;
for (auto &id : gr[v]) {
if (useless[id] == 1) continue;
int to = go(id, v);
if (used[to] == 1) {
chmin(up[v], in[to]);
}
else if (!used[to]) {
dfs(to);
chmin(up[v], up[to]);
if (up[to] >= in[to]) bridge[id] = 1;
}
}
used[v] = 2;
};
ve<int> p(n), rnk(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
rnk[i] = 1;
}
function<int(int)> par = [&p,&par](int v) {
if (p[v] == v) return v;
return p[v] = par(p[v]);
};
function<bool(int,int)> uni = [&p,&par,&rnk](int a, int b) {
a = par(a), b = par(b);
if (a == b) return 0;
if (rnk[a] > rnk[b]) swap(a, b);
p[a] = b, rnk[b] += rnk[a]; return 1;
};
dfs(0);
for (int i = 0; i < m; ++i) {
if (useless[i] == 1 || bridge[i]) continue;
uni(edges[i][0], edges[i][1]);
}
return par(0) != par(n - 1);
};
ll l = d0[n - 1], r = d0[n - 1] + sf[0], mid, ans;
while (l <= r) {
mid = l + r >> 1;
if (can(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
