#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector
const int N = 1000, K = 10, MX = (1<<K)-1;
vec<int> adj[N];
vec<array<int,3>> todo[N];
int par[N], dep[N], ind[N];
int dp[N][1<<K];
void dfs(int cur=0) {
for (int i=0;i<adj[cur].size();i++) {
int x = adj[cur][i];
ind[x] = i; par[x] = cur; dep[x] = dep[cur]+1;
adj[x].erase(find(adj[x].begin(),adj[x].end(),cur));
dfs(x);
}
}
int cost(const int cur, int targ, int& mask) {
int res = dp[targ][MX];
while (par[targ]!=cur) {
//if (cur==1 && targ==3) {cout << dp[par[targ]][MX^(1<<ind[targ])]-dp[targ][MX];}
res += dp[par[targ]][MX^(1<<ind[targ])]-dp[targ][MX];
targ = par[targ];
}
mask |= (1<<ind[targ]);
//if (cur==0 && targ==2) {cout<<res<<'\n';}
return res;
}
void upd(const int cur, const int mask, const int c) {
for (int i=MX;i>=0;i--) {
if (i&mask) {continue;}
chmax(dp[cur][mask|i],dp[cur][i]+c);
}
}
void dfs2(int cur=0) {
for (int x : adj[cur]) {
dfs2(x);
}
for (int x : adj[cur]) {
upd(cur,1<<ind[x],dp[x][MX]);
}
for (int i=0;i<todo[cur].size();i++) {
int a = todo[cur][i][0], b = todo[cur][i][1], c = todo[cur][i][2];
int mask = 0;
c += cost(cur,a,mask);
if (b!=-1) {c += cost(cur,b,mask);}
upd(cur,mask,c);
}
for (int mask=0;mask<(1<<K);mask++) {
for (int b=0;b<K;b++) {
chmax(dp[cur][mask|(1<<b)],dp[cur][mask]);
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
par[0] = -1; dep[0] = 0;
int n, m; cin >> n >> m;
vec<array<int,3>> non;
for (int i=0;i<m;i++) {
int a, b, c; cin >> a >> b >> c;
if (c!=0) {non.pb({--a,--b,c});}
else {
adj[--a].pb(--b); adj[b].pb(a);
}
} dfs();
int ans = 0;
for (int i=0;i<m-(n-1);i++) {
int a = non[i][0], b = non[i][1], c = non[i][2];
ans += c;
if (dep[a]<dep[b]) {swap(a,b);}
int dist = (dep[a]-dep[b])%2;
int a2 = a, b2 = b;
while (dep[a]!=dep[b]) {a = par[a];}
while (par[a]!=par[b]) {
a = par[a]; b = par[b];
}
if (dist==0) {
if (a==b) {todo[b].pb({a2,-1,c});}
else {todo[par[a]].pb({a2,b2,c});}
}
}
dfs2();
//cout << dp[2][MX^(1<<ind[4])]<<'\n';
//cout<<ans<<'\n';
//for (int i=0;i<n;i++) {cout<<dp[i][MX]<<' ';}
ans -= dp[0][MX];
cout << ans << '\n';
}
