#include <bits/stdc++.h>
using namespace std;
int n,m,sum,jump[1001][11],deg[1001],order[1001],lvl[1001],ptr,dp[1001][1<<10],mask1,mask2;
pair<int,int> par[1001]; vector<int> paths[1001];
struct Edge{
int a,b,c,lca; bool operator <(Edge x) const {return order[lca]<order[x.lca];}
}; vector <Edge> edges;
void dfs(int pos=1, int p=1){
jump[pos][0]=p;
for(auto el:paths[pos]){
if(el==p) continue; lvl[el]=lvl[pos]+1; par[el]={pos,1<<(deg[pos]++)}; dfs(el,pos);
}order[pos]=ptr++;
}
int Jump(int a, int b){
for(int j=0;j<=10;j++) if(b&(1<<j)) a=jump[a][j]; return a;
}
int LCA(int a, int b){
if(lvl[a]<lvl[b]) swap(a,b); a=Jump(a,lvl[a]-lvl[b]); if(a==b) return a;
for(int j=10;j>=0;j--) if(jump[a][j]!=jump[b][j]) a=jump[a][j],b=jump[b][j];
return jump[a][0];
}
void solve(){
for(auto edge:edges){
int a=edge.a,b=edge.b,cur=edge.c,lca=edge.lca;
if(lvl[a]%2 != lvl[b]%2 && cur!=0) continue;
for(mask1=0; a!=lca; tie(a,mask1)=par[a]) cur+=dp[a][mask1];
for(mask2=0; b!=lca; tie(b,mask2)=par[b]) cur+=dp[b][mask2]; mask1|=mask2;
for(int mask=(1<<deg[lca])-1;mask>=0;mask--){
if(mask&mask1) continue;
dp[lca][mask]=max(dp[lca][mask],cur+dp[lca][mask|mask1]);
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cin >>n>>m;
for(int i=1;i<=m;i++){
int a,b,c; cin >>a>>b>>c;
if(!c){
paths[a].push_back(b); paths[b].push_back(a);
}sum+=c; edges.push_back({a,b,c,0});
}par[1]={1,0}; dfs();
for(int j=1;j<=10;j++)
for(int i=1;i<=n;i++) jump[i][j]=jump[jump[i][j-1]][j-1];
for(auto &edge:edges){
if(lvl[edge.a]%2 != lvl[edge.b]%2 && edge.c!=0) continue;
edge.lca=LCA(edge.a,edge.b);
}sort(edges.begin(),edges.end());
solve(); cout <<sum-dp[1][0];
}
