#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define f first
// #define s second
#define pb(x) push_back(x)
#define int long long
const int MOD = 1e9+7;
const int inf = 1e9;
const int INF = 1e18+20;
const int LOG = 25;
struct edge {
int a, b, w;
};
int n, m;
bool dfs (int u, int par, int &weight, vector<int> &path, vector<vector<pair<int, int>>> &adj) {
if (u==n-1) {
path.push_back(u);
return true;
}
for (auto [v, w] : adj[u]) {
if (v==par) continue;
if (dfs(v, u, weight, path, adj)) {
weight+=w;
path.push_back(u);
return true;
}
}
return false;
}
void solve() {
cin>>n>>m;
vector<edge> edges(m);
for (int i=0; i<m; i++) {
int x, y, w;
cin>>x>>y>>w;
x--; y--;
edges[i] = {x, y, w};
/*adj[x].push_back({y, w});
adj[y].push_back({x, w});*/
}
auto key = [&](int x, int y) {
if (x>y) swap(x, y);
return (x<<32) | y;
};
map<int, int> p;
int mx = 0;
for (int i=m-1; i>=0; i--) {
int j = key(edges[i].a, edges[i].b);
p[j] = mx;
mx = max(mx, edges[i].w);
}
int ans=-1;
for (int x=0; x<m; x++) {
vector<vector<pair<int, int>>> adj(n);
for (int i=0; i<m; i++) {
int tt = edges[i].w;
if (i==x) {
int k = key(edges[i].a, edges[i].b);
tt += (p[k]);
}
int u = edges[i].a;
int v = edges[i].b;
adj[u].push_back({v, tt});
adj[v].push_back({u, tt});
}
vector<int> dist(n, INF);
dist[0]=0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (dist[u]!=d) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > d+w) {
dist[v]=d+w;
pq.push({dist[v],v});
}
}
}
ans=max(ans, dist[n-1]);
}
cout<<ans<<endl;
/*int weight=0;
vector<int> path;
dfs(0, -1, weight, path, adj);
int tt=-1;
for (int i=1; i<path.size(); i++) {
int j = key(path[i], path[i-1]);
tt= max(tt, p[j]);
}
weight+=tt;
cout<<weight<<endl;*/
}
bool multi=false;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
if (multi) cin>>t;
while (t--) solve();
return 0;
}
