#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;T f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=5007;
int n,m,cnt,h[N],dep[N],pa[N][14],id[N],reid[N],sum,f[N][N];
struct edge{int to,nxt;}mp[N<<1];
struct node{int u,v,w;};
vector<node>edg; vector<int>vct[N];
void add(int x,int y)
{
cnt++;
mp[cnt].nxt=h[x];
mp[cnt].to=y;
h[x]=cnt;
}
void prework(int x,int fa)
{
pa[x][0]=fa; dep[x]=dep[fa]+1;
for(int i=1;i<14;i++)
pa[x][i]=pa[pa[x][i-1]][i-1];
for(int i=h[x];i;i=mp[i].nxt)
if(mp[i].to!=fa)
prework(mp[i].to,x);
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int stp=dep[x]-dep[y];
for(int i=13;i>=0;i--)
if(stp>=(1<<i))
stp-=(1<<i),x=pa[x][i];
if(x==y) return x;
for(int i=13;i>=0;i--)
if(pa[x][i]!=pa[y][i])
x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
void solve(int x)
{
int son=0;
for(int i=h[x];i;i=mp[i].nxt)
{
int y=mp[i].to;
if(y==pa[x][0]) continue;
solve(y);
}
for(int i=h[x];i;i=mp[i].nxt)
{
int y=mp[i].to;
if(y==pa[x][0]) continue;
id[son]=y; reid[y]=1<<son; son++;
}
for(int S=0,now=0;S<(1<<son);S++,now=0)
{
for(int i=0;i<son;i++)
if(!((S>>i)&1))
now+=f[id[i]][0];
f[x][S]=now;
}
for(int k=vct[x].size()-1;k>=0;k--)
{
int i=vct[x][k],now=edg[i].w,a=0,b=0;
if(edg[i].u!=x) now+=f[edg[i].u][0];
if(edg[i].v!=x) now+=f[edg[i].v][0];
if(edg[i].u!=x)
for(a=edg[i].u;pa[a][0]!=x;a=pa[a][0])
now+=f[pa[a][0]][reid[a]];
if(edg[i].v!=x)
for(b=edg[i].v;pa[b][0]!=x;b=pa[b][0])
now+=f[pa[b][0]][reid[b]];
for(int S=0;S<(1<<son);S++)
if((S&reid[a])==0&&(S&reid[b])==0)
f[x][S]=max(f[x][S],f[x][S|reid[a]|reid[b]]+now);
}
}
int main()
{
read(n,m);
for(int i=1,x,y,z;i<=m;i++)
{
read(x,y,z); sum+=z;
if(z==0) add(x,y),add(y,x);
else edg.push_back((node){x,y,z});
}
prework(1,0);
for(int i=0;i<edg.size();i++)
{
auto [x,y,z]=edg[i];
int lca=LCA(x,y);
if(!((dep[x]+dep[y]-2*dep[lca])&1))
vct[lca].push_back(i);
}
solve(1); print(sum-f[1][0],'\n');
return 0;
}
