#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxn = 3e5+5;
const ll inf = 1e16;
struct Edge {
int to, id;
};
int n, m;
vector<Edge> adj[mxn];
ll W[mxn];
ll get_min_dist() {
vector<long long> dist(n+1, inf);
priority_queue<pair<ll, int>> pq;
dist[1] = 0;
pq.push({-dist[1], 1});;
while(!pq.empty()) {
ll d = -pq.top().first;
int a = pq.top().second;
pq.pop();
if(dist[a] != d) continue;
for(auto e : adj[a]) if(dist[e.to] > d+W[e.id]) {
dist[e.to] = d+W[e.id];
pq.push({-dist[e.to], e.to});
}
}
return dist[n];
}
int main(int argc, char const *argv[]) {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b; cin >> a >> b >> W[i];
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
ll mxw = W[m], ans = 0;
for(int i = m-1; i >= 1; i--) {
W[i] += mxw;
ans = max(ans, get_min_dist());
W[i] -= mxw;
mxw = max(mxw, W[i]);
}
cout << ans << "\n";
return 0;
}
