#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int n,m,num,ans,sum,dep[N],f[N][N],s[N][11],fa[N],cnt[N],p[N];
vector<int>v[N],t[N];
struct edge{int x,y,w,xt,yt;}e[N*5];
void dfs(int x,int y)
{
for(int i:v[x])
if(i!=y)
fa[i]=x,p[i]=cnt[x],s[x][cnt[x]++]=i,
dep[i]=dep[x]+1,dfs(i,x);
}
void solve(int x)
{
for(int i=0;i<cnt[x];i++)
solve(s[x][i]);
for(int i:t[x])
{
int res=0,xx=e[i].x,yy=e[i].y;
if(x==xx)
{
res+=f[yy][(1<<cnt[yy])-1];
while(fa[yy]!=x)res+=f[fa[yy]][((1<<cnt[fa[yy]])-1)^(1<<p[yy])],yy=fa[yy];
}
else
{
res+=f[xx][(1<<cnt[xx])-1];
res+=f[yy][(1<<cnt[yy])-1];
while(fa[xx]!=x)res+=f[fa[xx]][((1<<cnt[fa[xx]])-1)^(1<<p[xx])],xx=fa[xx];
while(fa[yy]!=x)res+=f[fa[yy]][((1<<cnt[fa[yy]])-1)^(1<<p[yy])],yy=fa[yy];
}
e[i].w+=res,e[i].xt=xx,e[i].yt=yy;
// cout<<x<<' '<<e[i].x<<' '<<e[i].y<<' '<<p[xx]<<' '<<p[yy]<<' '<<e[i].w<<endl;
}
for(int i=0;i<(1<<cnt[x]);i++)
for(int j=0;j<cnt[x];j++)
if((i>>j)&1)f[x][i]+=f[s[x][j]][(1<<cnt[s[x][j]])-1];
for(int i=0;i<(1<<cnt[x]);i++)
{
for(int j:t[x])
{
if(e[j].xt==x&&(!((i>>p[e[j].yt])&1)))
f[x][i|(1<<p[e[j].yt])]=max(f[x][i|(1<<p[e[j].yt])],f[x][i]+e[j].w);
else if((!((i>>p[e[j].yt])&1))&&(!((i>>p[e[j].xt])&1)))
f[x][i|(1<<p[e[j].yt])|(1<<p[e[j].xt])]=
max(f[x][i|(1<<p[e[j].yt])|(1<<p[e[j].xt])],f[x][i]+e[j].w);
}
}
// cout<<x<<' '<<f[x][(1<<cnt[x])-1]<<endl;
}
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(z==0)v[x].push_back(y),v[y].push_back(x);
else e[++num]={x,y,z,0,0};
}
dfs(1,0);
for(int i=1;i<=num;i++)
{
if(dep[e[i].x]%2!=dep[e[i].y]%2)
{ans+=e[i].w;continue;}
sum+=e[i].w;
if(dep[e[i].x]>dep[e[i].y])swap(e[i].x,e[i].y);
int xx=e[i].x,yy=e[i].y;
while(xx!=yy)
{
if(dep[xx]<dep[yy])
swap(xx,yy);
xx=fa[xx];
}
t[xx].push_back(i);
// cout<<e[i].x<<' '<<e[i].y<<' '<<e[i].w<<' '<<xx<<endl;
}
// cout<<ans<<endl;
solve(1);
ans+=sum-f[1][(1<<cnt[1])-1];
printf("%d\n",ans);
}
