#include <bits/stdc++.h>
using namespace std;
struct edge{ int a, b, w; };
const int mx = 1005;
int n, m, ans, dep[mx], cnt, par[mx], pos[mx], deg[mx], dp[mx][(1<<10)];
vector<int> adj[mx]; vector<edge> noPave, evenPth[mx];
void dfs(int i){
for (int x : adj[i])
if (x != par[i])
dep[x] = dep[i]+1, par[x] = i, pos[x] = (1<<deg[i]++), dfs(x);
}int LCA(int a, int b){
while (dep[a] > dep[b]) a = par[a];
while (dep[b] > dep[a]) b = par[b];
while (a != b) a = par[a], b = par[b];
return a;
}void solve(int i){
for (int x : adj[i])
if (x != par[i])
solve(x);
for (int msk = 0; msk < (1<<deg[i]); msk++)
for (int x : adj[i])
if (x != par[x] and !(msk&pos[x]))
dp[i][msk] += dp[x][0];
for (auto r : evenPth[i]){
int sum = r.w, p1 = 0, p2 = 0;
for (int x = r.a; x != i; p1 = pos[x], x = par[x]) sum += dp[x][p1];
for (int x = r.b; x != i; p2 = pos[x], x = par[x]) sum += dp[x][p2];
for (int msk = 0; msk < (1<<deg[i]); msk++)
if (!(msk&p1) and !(msk&p2))
dp[i][msk] = max(dp[i][msk], dp[i][(msk|p1|p2)]+sum);
}
}
int main(){
cin >> n >> m;
for (int i = 0; i < m; i++){
int a, b, w; cin >> a >> b >> w; ans += w;
if (!w) adj[a].push_back(b), adj[b].push_back(a);
else noPave.push_back({a, b, w});
}dfs(1);
for (auto r : noPave)
if ((dep[r.a]+dep[r.b])%2 == 0)
evenPth[LCA(r.a, r.b)].push_back(r);
solve(1); cout<<ans-dp[1][0]<<endl;
}
