#include <bits/stdc++.h>
using namespace std;
long long dp[5001][(1<<10)];
int in[5001],ou[5001],lol[5001],deg[5001];
vector<int> adj[5001];pair<int,int> pr[5001];
struct road{
int l,r,cost,lca;
};
bool operator<(road a,road b){
return ou[a.lca]<ou[b.lca];
}
int timer = 0;
void dfs(int i,int Pr){
in[i] = ++timer;
lol[i] = lol[Pr]^1;
for(auto j:adj[i]){
if(j!=Pr){
pr[j] = {i,(1<<deg[i])};
deg[i]++;
dfs(j,i);
}
}
ou[i] = ++timer;
}
bool ispar(int A,int B){
return ((in[A]<=in[B]&&ou[A]>=ou[B]));
}
int lca(int A,int B){
while(!ispar(A,B))A = pr[A].first;
return A;
}
int main(){
//ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector<road> v;
long long all = 0;
for(int i = 0;i<m;i++){
int a,b,c;cin>>a>>b>>c;all+=c;
if(!c){
adj[a].push_back(b);
adj[b].push_back(a);
}
v.push_back({a,b,c});
}
dfs(1,0);
for(int i = 0;i<v.size();i++){
v[i].lca = lca(v[i].l,v[i].r);
}
sort(v.begin(),v.end());
for(auto i:v){
if(i.cost&&(lol[i.l]^lol[i.r])==1)continue;
long long xd = i.cost;
pair<int,int> A , B;
for(A = {i.l,0};A.first!=i.lca;A = pr[A.first])xd+=dp[A.first][A.second];
for(B = {i.r,0};B.first!=i.lca;B = pr[B.first])xd+=dp[B.first][B.second];
for(int mask = (1<<deg[i.lca])-1;~mask;mask--){
if((mask&(A.second|B.second))==0){
dp[i.lca][mask] = max(dp[i.lca][mask],xd+dp[i.lca][mask|A.second|B.second]);
}
}
}
cout<<all-dp[1][0]<<endl;
}
