#include <bits/stdc++.h>
using namespace std;
// Constants
const int MAXN = 5001;
const int MAXK = 10;
// Global variables
vector<vector<int>> dp(MAXN, vector<int>(1 << MAXK, 0));
vector<int> in_time(MAXN, 0), out_time(MAXN, 0), lol(MAXN, 0), deg(MAXN, 0);
vector<pair<int, int>> pr(MAXN, {0, 0});
vector<vector<int>> adj(MAXN);
int timer = 0;
struct Road {
int l, r, cost, lca;
Road(int l, int r, int cost, int lca = 0) : l(l), r(r), cost(cost), lca(lca) {}
bool operator<(const Road &other) const {
return out_time[lca] < out_time[other.lca];
}
};
void reset_globals() {
fill(dp.begin(), dp.end(), vector<int>(1 << MAXK, 0));
fill(in_time.begin(), in_time.end(), 0);
fill(out_time.begin(), out_time.end(), 0);
fill(lol.begin(), lol.end(), 0);
fill(deg.begin(), deg.end(), 0);
fill(pr.begin(), pr.end(), make_pair(0, 0));
for (auto &v : adj) v.clear();
timer = 0;
}
void dfs(int node, int parent) {
++timer;
in_time[node] = timer;
lol[node] = lol[parent] ^ 1;
for (int neighbor : adj[node]) {
if (neighbor != parent) {
pr[neighbor] = {node, 1 << deg[node]};
++deg[node];
dfs(neighbor, node);
}
}
++timer;
out_time[node] = timer;
}
bool is_parent(int A, int B) {
return in_time[A] <= in_time[B] && out_time[A] >= out_time[B];
}
int find_lca(int A, int B) {
while (!is_parent(A, B)) {
A = pr[A].first;
}
return A;
}
int solve(int n, int m, vector<tuple<int, int, int>> &road_data) {
vector<Road> roads;
int total_cost = 0;
for (const auto &[a, b, c] : road_data) {
total_cost += c;
if (c == 0) {
adj[a].push_back(b);
adj[b].push_back(a);
}
roads.emplace_back(a, b, c);
}
dfs(1, 0);
for (auto &road : roads) {
road.lca = find_lca(road.l, road.r);
}
sort(roads.begin(), roads.end());
for (const auto &road : roads) {
if (road.cost && (lol[road.l] ^ lol[road.r]) == 1) {
continue;
}
int cost_accumulated = road.cost;
pair<int, int> A = {road.l, 0}, B = {road.r, 0};
while (A.first != road.lca) {
cost_accumulated += dp[A.first][A.second];
A = pr[A.first];
}
while (B.first != road.lca) {
cost_accumulated += dp[B.first][B.second];
B = pr[B.first];
}
for (int mask = (1 << deg[road.lca]) - 1; mask >= 0; --mask) {
if ((mask & (A.second | B.second)) == 0) {
dp[road.lca][mask] = max(
dp[road.lca][mask],
cost_accumulated + dp[road.lca][mask | A.second | B.second]
);
}
}
}
return (total_cost - dp[1][0]);
}
int main() {
int n, m;
cin >> n >> m;
vector<tuple<int, int, int>> road_data(m);
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
road_data[i] = {a, b, c};
}
reset_globals();
cout << solve(n, m, road_data) << endl;
return 0;
}
