#include <bits/stdc++.h>
using namespace std;
const int nx=1e3+5, kx=10;
int n, m, u, v, w, dp[nx][1<<kx], lvl[nx], pa[nx][kx], idx[nx], sz[nx], res;
vector<int> d[nx];
vector<tuple<int, int, int>> edg, event[nx];
void dfs(int u, int p)
{
lvl[u]=lvl[p]+1;
pa[u][0]=p;
for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
for (auto v:d[u]) if (v!=p) idx[v]=sz[u]++, dfs(v, u);
}
int lca(int u, int v)
{
if (lvl[u]>lvl[v]) swap(u, v);
for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
if (u==v) return u;
for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
return pa[u][0];
}
void solve(int u, int p)
{
for (auto v:d[u]) if (v!=p) solve(v, u), dp[u][1<<idx[v]]=dp[v][(1<<sz[v])-1];
for (auto [cu, cv, cw]:event[u])
{
int umsk=0, sm=0, pv=-1;
while (cu!=u)
{
int msk=(1<<sz[cu])-1;
if (pv!=-1) msk^=(1<<idx[pv]);
pv=cu;
sm+=dp[cu][msk];
if (pa[cu][0]==u) umsk^=(1<<idx[cu]);
cu=pa[cu][0];
}
pv=-1;
while (cv!=u)
{
int msk=(1<<sz[cv])-1;
if (pv!=-1) msk^=(1<<idx[pv]);
pv=cv;
sm+=dp[cv][msk];
if (pa[cv][0]==u) umsk^=(1<<idx[cv]);
cv=pa[cv][0];
}
dp[u][umsk]=max(dp[u][umsk], sm+cw);
}
for (int msk=0; msk<(1<<sz[u]); msk++) for (int j=msk; j>0; j=(j-1)&msk) dp[u][msk]=max(dp[u][msk], dp[u][j]+dp[u][msk^j]);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++)
{
cin>>u>>v>>w;
if (!w) d[u].push_back(v), d[v].push_back(u);
else edg.push_back({u, v, w});
}
dfs(1, 1);
for (auto [u, v, w]:edg)
{
if ((lvl[u]+lvl[v]-2*lvl[lca(u, v)])%2) res+=w;
else event[lca(u, v)].push_back({u, v, w}), res+=w;
}
solve(1, 1);
cout<<res-dp[1][(1<<sz[1])-1];
}
