#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1001, M = 5001, K = 10;
int n, m, sum;
pii par[N];
int anc[N][K + 1];
vector<int> paths[N];
int deg[N], order[N], depth[N], ptr;
struct Edge {
int a, b, c, lca;
bool operator<(const Edge &x) const { return order[lca] < order[x.lca]; }
};
vector<Edge> edges;
void dfs(int u, int p) {
anc[u][0] = p;
for (auto &v : paths[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1, par[v] = {u, 1 << (deg[u]++)};
dfs(v, u);
}
order[u] = ptr;
ptr++;
}
int ancestor(int a, int d) {
for (int j = 0; j <= K; j++) {
if (d & (1 << j)) a = anc[a][j];
}
return a;
}
int LCA(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = ancestor(a, depth[a] - depth[b]);
if (a == b) return a;
for (int j = K; j >= 0; j--) {
if (anc[a][j] != anc[b][j]) a = anc[a][j], b = anc[b][j];
}
return anc[a][0];
}
int dp[N][1 << K];
void solve2() {
for (auto &e : edges) {
int a = e.a, b = e.b, cur = e.c, lca = e.lca;
if (depth[a] % 2 != depth[b] % 2 && cur != 0) continue;
int mask1, mask2;
for (mask1 = 0; a != lca; tie(a, mask1) = par[a]) {
cur += dp[a][mask1];
}
for (mask2 = 0; b != lca; tie(b, mask2) = par[b]) {
cur += dp[b][mask2];
}
mask1 |= mask2;
for (int mask = (1 << deg[lca]) - 1; mask >= 0; mask--) {
if (mask & mask1) continue;
dp[lca][mask] = max(dp[lca][mask], cur + dp[lca][mask | mask1]);
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (!c) paths[a].push_back(b), paths[b].push_back(a);
sum += c;
edges.push_back({a, b, c, 0});
}
par[1] = {1, 0};
dfs(1, 1);
for (int j = 1; j <= K; j++) {
for (int i = 1; i <= n; i++) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
}
for (auto &edge : edges) {
if (depth[edge.a] % 2 != depth[edge.b] % 2 && edge.c != 0) continue;
edge.lca = LCA(edge.a, edge.b);
}
sort(edges.begin(), edges.end());
solve2();
cout << sum - dp[1][0] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
