#include
using namespace std;
const int buf_len = 4567;
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() {
if (++ bufb == bufe)
bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin);
}
#define readInt(x) {
register int s(0);
do {
readBuf();
} while (!isdigit(*bufb));
do {
s = s * 10 + *bufb - 48;
readBuf();
} while (isdigit(*bufb));
x = s;
}
const int maxn = 209; const int inf = 0x3f3f3f3f;
int n, m, g[maxn][maxn], a[maxn][maxn], rk[maxn][maxn];
#define upAns(x) (ans=min(ans,x))
int main() { readInt(n); readInt(m); memset(g, 0x3f, sizeof(g)); for (int i = 0; i < m; ++ i) { int u, v, w; readInt(u); readInt(v); readInt(w); g[u][v] = g[v][u] = min(g[u][v], w); } memcpy(a, g, sizeof(a)); for (int k = 1; k <= n; ++ k) for (int i = 1; i <= n; ++ i) if (i ^ k) for (int j = 1; j <= n; ++ j) if ((i ^ k) && (k ^ j)) a[i][j] = min(a[i][j], a[i][k] + a[k][j]); for (int i = 1; i <= n; ++ i) a[i][i] = 0; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) rk[i][j] = j; for (int j = 1; j <= n; ++ j) for (int k = j + 1; k <= n; ++ k) if (a[i][rk[i][j]] < a[i][rk[i][k]]) swap(rk[i][j], rk[i][k]); } int ans(inf); for (int u = 1; u <= n; ++ u) for (int v = u; v <= n; ++ v) if (g[u][v] < inf) { int br(a[rk[u][1]][v]); for (int i = 2; i <= n; ++ i) { int bl(a[rk[u][i]][u]); int xn(br - bl + g[u][v]); if (xn >= 0 && xn <= g[u][v] * 2) upAns(bl * 2 + xn); br = max(br, a[rk[u][i]][v]); } } printf("%d\n", ans); }