#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
vector<array<int, 3>> vai3;
int tot = 0;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
if (c == 0) {
adj[a].push_back(b), adj[b].push_back(a);
} else {
tot += c;
vai3.push_back({a, b, c});
}
}
vector<int> dep(n);
vector<int> parvi(n);
vector<int> which(n);
int curd = 0;
function<void(int, int, int)> fvii = [&](int cur, int par, int in) {
dep[cur] = curd;
which[cur] = in;
parvi[cur] = par;
for (int i = 0; i < adj[cur].size(); i++)
if (adj[cur][i] == par) {
swap(adj[cur][i], adj[cur].back());
}
if (par != -1)
adj[cur].pop_back();
for (int i = 0; i < adj[cur].size(); i++) {
curd++;
fvii(adj[cur][i], cur, i);
curd--;
}
};
fvii(0, -1, -1);
vector<array<int, 3>> vai32;
for (auto [a, b, c] : vai3) {
if (dep[a] % 2 == dep[b] % 2)
vai32.push_back({a, b, c});
}
vai3.swap(vai32);
vector<vector<int>> lca(n);
vector<vector<pair<int, int>>> vvpii;
for (int i = 0; i < vai3.size(); i++) {
auto [a, b, c] = vai3[i];
vvpii.emplace_back();
if (dep[a] > dep[b])
swap(a, b);
while (dep[a] < dep[b]) {
if (parvi[b] == a) {
vvpii.back().emplace_back(parvi[b], 1 << which[b]);
} else
vvpii.back().emplace_back(parvi[b], ((1 << adj[parvi[b]].size()) - 1) ^
(1 << which[b]));
b = parvi[b];
}
while (a != b) {
if (parvi[a] == parvi[b]) {
vvpii.back().emplace_back(parvi[a], (1 << which[b]) ^ (1 << which[a]));
} else {
vvpii.back().emplace_back(parvi[a], ((1 << adj[parvi[a]].size()) - 1) ^
(1 << which[a]));
vvpii.back().emplace_back(parvi[b], ((1 << adj[parvi[b]].size()) - 1) ^
(1 << which[b]));
}
a = parvi[a], b = parvi[b];
}
lca[a].push_back(i);
}
vector<vector<int>> dp(n);
function<void(int)> dfs2 = [&](int cur) {
for (auto a : adj[cur]) {
dfs2(a);
}
dp[cur].resize(1 << adj[cur].size());
vector<int> lcaval(lca[cur].size());
for (int i = 0; i < lca[cur].size(); i++) {
int in = lca[cur][i];
lcaval[i] = vai3[in][2];
if (vai3[in][0] != vvpii[in].back().first)
lcaval[i] += dp[vai3[in][0]].back();
if (vai3[in][1] != vvpii[in].back().first)
lcaval[i] += dp[vai3[in][1]].back();
for (int j = 0; j + 1 < vvpii[in].size(); j++) {
lcaval[i] += dp[vvpii[in][j].first][vvpii[in][j].second];
}
}
for (int i = 0; i < dp[cur].size(); i++) {
for (int j = 0; j < lca[cur].size(); j++) {
int in = lca[cur][j];
if ((i & vvpii[in].back().second) == vvpii[in].back().second)
dp[cur][i] =
max(dp[cur][i], dp[cur][i ^ vvpii[in].back().second] + lcaval[j]);
}
int val = 0;
for (int j = 0; j < adj[cur].size(); j++) {
if ((1 << j) & i)
val += dp[adj[cur][j]].back();
}
dp[cur][i] = max(dp[cur][i], val);
}
};
dfs2(0);
cout << tot - dp[0].back() << "\n";
}
