#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int n, m, par[maxn][maxn], len[maxn], suf[maxn], mx[maxn];
bool mark[maxn];
vector<int> G[maxn];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
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, int d) -> void {
diam = max(diam, d), par[i][u] = fa;
for (int v : G[u]) if (v ^ fa) self(self, v, u, d + 1);
};
dfs(dfs, i, -1, 0);
}
int ans = 2 * (n - 1) - diam;
for (auto &e : E) {
int u = e[0], v = e[1], mn = INT_MAX;
memset(mark, 0, sizeof(mark));
vector<int> path;
for (int i = u; ; i = par[v][i]) {
path.push_back(i), mark[i] = 1;
if (i == v) break;
}
for (int i = 0; i < path.size(); i++) {
auto dfs = [&](auto self, int u, int fa) -> void {
mx[u] = 0;
int sec = 0;
for (int v : G[u]) if (!mark[v] && v ^ fa) {
self(self, v, u);
if (mx[v] + 1 > mx[u]) sec = mx[u], mx[u] = mx[v] + 1;
else if (mx[v] + 1 > sec) sec = mx[v] + 1;
}
mn = min(mn, 2 * (n - 2) - (int)path.size() + 3 - mx[u] - sec);
};
dfs(dfs, path[i], -1), len[i] = mx[path[i]];
}
for (int i = path.size() - 1; ~i; i--) {
suf[i] = max((int)path.size() - i - 1 + len[i], i + 1 == path.size() ? 0 : suf[i + 1]);
}
for (int i = 0, mx = 0; i + 1 < path.size(); i++) {
mx = max(mx, i + len[i]);
mn = min(mn, 2 * (n - 2) - mx - suf[i + 1]);
}
ans = min(ans, mn + e[2]);
}
cout << ans << "\n";
return 0;
}
