// Credit : tphuocdz
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int K=10;
const int N=(1<<10);
const int INF=1e18;
int p[N+1],d[N+1],far[N+1][K+1],dp[N+1][N+1];
vector <pair <int,int>> adj[N+1];
vector <tuple <int,int,int>> k[N+1];
void cal(int u){
for(int i=1;i<=K;i++){
far[u][i]=far[far[u][i-1]][i-1];
}
}
void dfs(int u,int par){
d[u]=d[par]+1;
far[u][0]=par;
cal(u);
p[u]=par;
for(auto [v,w]:adj[u]){
if(w>0 || v==par) continue;
dfs(v,u);
}
}
void goto_dep(int &a,int dep){
if(d[a]==dep) return ;
int akt=0;
while(d[far[a][akt+1]]>dep) akt++;
a=far[a][akt];
goto_dep(a,dep);
}
int lca(int a,int b){
if(d[a]>d[b]) swap(a,b);
goto_dep(b,d[a]);
while(a!=b){
int akt=0;
while(far[a][akt+1]!=far[b][akt+1]) akt++;
a=far[a][akt];
b=far[b][akt];
}
return a;
}
void fix(int u){
vector <pair <int,int>> n;
for(auto [v,w]:adj[u]){
int l=lca(u,v);
int dis=d[u]+d[v]-2*d[l];
if(dis%2==0 || w==0){
n.push_back({v,w});
if(u<v && w>0) k[l].push_back({u,v,w});
}
}
adj[u]=n;
}
int rec(int u,int pp,int x,pair <int,int> &dz){
if(u==x){
if(dz.first==-1) dz.first=pp;
else dz.second=pp;
return 0;
}
int idx=N-1,t=-1;
for(auto [v,w]:adj[u]){
t++;
if(v==p[u] || w>0) continue;
if(v==pp) idx-=(1<<t);
}
return dp[u][idx]-dp[pp][N-1]+rec(p[u],u,x,dz);
}
void solve(int u,int par){
for(auto [v,w]:adj[u]){
if(w>0 || v==par) continue;
solve(v,u);
}
for(int i=0;i<N;i++){
int t=-1;
for(auto [v,w]:adj[u]){
t++;
if(v==par || w>0) continue;
dp[u][i]+=dp[v][N-1];
}
}
for(auto [a,b,val]:k[u]){
pair <int,int> dz={-1,-1};
int idx=0,w=rec(a,-1,u,dz)+rec(b,-1,u,dz),t=-1,odj=0;
for(auto [v,w]:adj[u]){
t++;
if(v==par || w>0) continue;
if(v==dz.first || v==dz.second){
idx+=(1<<t);
odj+=dp[v][N-1];
}
}
for(int i=0;i<N;i++){
if((i&idx)==idx){
dp[u][i]=max(dp[u][i],dp[u][i^idx]+val-odj+w);
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
int s=0;
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
s+=w;
}
dfs(1,1);
for(int i=1;i<=n;i++) fix(i);
solve(1,1);
int ans=0;
for(int i=0;i<N;i++) ans=max(ans,dp[1][i]);
cout << s-ans;
}
