#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>;
int32_t main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<vector<Edge>> adj(n);
vector<Edge> edge(m);
for (int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w; u--, v--;
if (u == v) continue;
adj[u].push_back({v, w, i}); adj[v].push_back({u, w, i});
edge[i] = Edge{u, v, w};
}
vector<int> suff(m+1, 0);
for (int i = m-1; i > -1; i--) suff[i] = max(suff[i], edge[i][2]);
pii ans;
auto dfs = [&](auto&& self, int s, int pi, int W, int idx) -> void{
if (s == n-1) ans = {W, idx};
for (auto [u, w, i] : adj[s]) if (u != pi) self(self, u, s, W + w, min(idx, i));
}; dfs(dfs, 0, 0, 0, 0);
cout << ans.ff + suff[ans.ss + 1] << endl;
return 0;
}
