#include <bits/stdc++.h>
using namespace std;
struct edge {
int a, b, c, lca;
};
vector<edge> edges, fe;
int total = 0;
vector<int> adj[1005];
int tin[1005], timer = 1;
int jmp[1005][12], depth[1005];
int col[1005];
pair<int, int> par[1005];
int deg[1005];
int dp[1005][1 << 11];
void dfs(int node) {
tin[node] = timer++;
for (int i = 1; i < 12; i++) jmp[node][i] = jmp[jmp[node][i-1]][i-i];
for (auto nxt : adj[node]) {
if (tin[nxt]) continue;
if (col[node] == 1) {
col[nxt] = 2;
} else col[nxt] = 1;
par[nxt] = {node, (1 << deg[node]++)};
depth[nxt] = depth[node] + 1;
jmp[nxt][0] = node;
dfs(nxt);
}
}
int lca(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
for (int i = 11; i >= 0; i--) {
if (depth[jmp[b][i]] >= depth[a]) b = jmp[b][i];
}
if (a == b) return a;
for (int i = 11; i >= 0; i--) {
if (jmp[a][i] != jmp[b][i]) {
a = jmp[a][i]; b = jmp[b][i];
}
}
return jmp[a][0];
}
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
total += c;
if (c == 0) {
adj[a].push_back(b); adj[b].push_back(a);
}
edges.push_back({a, b, c});
}
col[1] = 1;
jmp[1][0] = 1;
depth[1] = 1;
dfs(1);
for (auto e: edges) {
if (col[e.a] == col[e.b]) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
else if (e.c == 0) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
}
sort(fe.begin(), fe.end(), [&](edge a, edge b) {
return tin[a.lca] > tin[b.lca];
});
for (auto e : fe) {
int tot = e.c;
int finalmask = 0;
int mask = 0;
for (int i = e.a; i != e.lca; mask = par[i].second, i = par[i].first) {
tot += dp[i][mask];
}
finalmask |= mask;
mask = 0;
for (int i = e.b; i != e.lca;mask = par[i].second, i = par[i].first) {
tot += dp[i][mask];
}
finalmask |= mask;
for (int mk = (1 << deg[e.lca]) - 1; mk >= 0 ; mk--) {
if (mk & finalmask) continue;
dp[e.lca][mk] = max(dp[e.lca][mk], dp[e.lca][mk | finalmask] + tot);
}
}
cout << total - dp[1][0];
}
