#include<bits/stdc++.h>
using namespace std;
inline bool getbit(int num, int bit)
{
return (num >> bit)&1;
}
inline int flipbit(int num, int bit)
{
return num ^ (1 << bit);
}
vector<int> ad[1005], child[1005];
int h[1005], par[1005];
bool visited[1005];
void dfs(int u)
{
visited[u] = 1;
for(int v : ad[u]) if(visited[v] == 0){
child[u].push_back(v); par[v] = u; h[v] = h[u] + 1;
dfs(v);
}
visited[u] = 0;
}
vector<pair<pair<int, int>, int>> path[1005];
int cost[1005][1005], dp[1005][1005];
int lca(int u, int v)
{
int reu = u, rev = v;
while(u != v){
if(h[u] < h[v]) swap(u, v);
u = par[u];
}
return u;
}
void update_cost(int u, int v, int r, int c)
{
if(h[u] > h[v]) swap(u, v);
if(u == r){
int cur = c, lastv = 0;
while(true){
cur += dp[v][lastv];
lastv = v; v = par[v]; if(v == u) break;
}
v = lastv;
cost[v][v] = max(cost[v][v], cur);
}
else{
int cur = c, lastu = 0;
while(true){
cur += dp[u][lastu];
lastu = u; u = par[u]; if(u == r) break;
}
int lastv = 0;
while(true){
cur += dp[v][lastv];
lastv = v; v = par[v]; if(v == r) break;
}
u = lastu; v = lastv;
cost[u][v] = max(cost[u][v], cur);
cost[v][u] = max(cost[v][u], cur);
}
}
void dfsdp(int u)
{
for(int v : child[u]) dfsdp(v);
int m = child[u].size();
/*Update for all path*/
for(auto &i : path[u]){
update_cost(i.first.first, i.first.second, u, i.second);
}
/*Dp bitmask*/
vector<int> f(1);
for(int i = 0; i < m; i++){
vector<int> g(1 << (i+1));
for(int b = 0; b < g.size(); b++){
if(getbit(b, i) == 1) g[b] = f[flipbit(b, i)];
else g[b] = f[b];
if(getbit(b, i) == 1){
for(int j = 0; j <= i; j++) if(getbit(b, j) == 1){
int target = flipbit(b, i);
if(i != j) target = flipbit(target, j);
g[b] = max(g[b], f[target] + cost[child[u][i]][child[u][j]]);
}
}
}
f = g;
}
/*cerr<<"A"<<u<<endl;
for(int j : f) cerr<<j<<" ";
cerr<<endl;*/
/*Update dp*/
for(int b = 0; b < f.size(); b++){
for(int i = 0; i < m; i++) if(getbit(b, i) == 0){
int cost = f[b];
for(int j = 0; j < m; j++) if(i != j && getbit(b, j) == 0) cost += dp[child[u][j]][0];
dp[u][child[u][i]] = max(dp[u][child[u][i]], cost);
}
int cost = f[b];
for(int j = 0; j < m; j++) if(getbit(b, j) == 0) cost += dp[child[u][j]][0];
dp[u][0] = max(dp[u][0], cost);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin>>n>>m;
vector<pair<pair<int, int>, int>> edges;
for(int i = 1; i <= m; i++){
int u, v, c; cin>>u>>v>>c;
if(c == 0){
ad[u].push_back(v);
ad[v].push_back(u);
}
else{
edges.push_back({{u, v}, c});
}
}
dfs(1);
int ans = 0;
/*Preprocess path*/
for(auto &i : edges){
int u = i.first.first, v = i.first.second;
ans += i.second;
if(h[u]%2 == h[v]%2) path[lca(u, v)].push_back({{u, v}, i.second});
}
/*Dp*/
dfsdp(1);
/*for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cerr<<cost[i][j]<<" ";
cerr<<endl;
}*/
int minu = 0;
for(int i = 0; i <= n; i++) minu = max(minu, dp[1][i]);
cout<<ans-minu;
}
