#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int n, m, d[maxn][maxn], par[maxn][maxn];
vector<int> G[maxn];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
assert(n <= 5000 && m <= 10000);
vector<array<int, 3>> E;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
if (w == 1) G[u].push_back(v), G[v].push_back(u);
else if (w < (n + 1) / 2) E.push_back({u, v, w});
}
int diam = 0;
for (int i = 0; i < n; i++) {
auto dfs = [&](auto self, int u, int fa) -> void {
diam = max(diam, d[i][u]), par[i][u] = fa;
for (int v : G[u]) if (v ^ fa) {
d[i][v] = d[i][u] + 1, self(self, v, u);
}
};
dfs(dfs, i, -1);
}
int ans = 2 * (n - 1) - diam;
for (auto &e : E) {
int u = e[0], v = e[1], mn = INT_MAX;
for (int i = 0; i < n; i++) if (i ^ u) {
for (int j = 0; j < n; j++) if (j ^ v) {
int cnt = 0;
for (int k = 0; k < n; k++) {
if (d[u][k] + d[k][i] == d[u][i] && d[v][k] + d[k][j] == d[v][j]) cnt++;
}
mn = min(mn, 2 * (n + cnt - 2) - d[u][i] - d[v][j]);
}
}
ans = min(ans, mn + e[2]);
}
cout << ans << "\n";
return 0;
}
