#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
#define vtiii vector<tiii>
const int K = 10, N = (1 << (K)), MOD = 1e9 + 7, INF = int(1e18);
int p[N], d[N], far[N][K + 1];
int dp[N][N];
vpi graf[N];
vtii k[N];
void calc_far(int u){
for(int i = 1; i <= K; i++){
far[u][i] = far[far[u][i - 1]][i - 1];
}
}
void dfs(int u, int v){
d[u] = d[v] + 1;
far[u][0] = v;
calc_far(u);
p[u] = v;
for(auto [i, j] : graf[u]){
if(j > 0 || i == v) continue;
dfs(i, u);
}
}
void go_to_dep(int &a, int dep){
if(d[a] == dep) return;
int akt = 0;
while(d[far[a][akt + 1]] > dep) akt++;
a = far[a][akt];
go_to_dep(a, dep);
}
int lca(int a, int b){
if(d[a] > d[b]) swap(a, b);
go_to_dep(b, d[a]);
while(a != b){
int akt = 0;
while(far[a][akt + 1] != far[b][akt + 1]) akt++;
a = far[a][akt]; b = far[b][akt];
}
return a;
}
void fix(int u){
vpi n;
for(auto [i, j] : graf[u]){
int l = lca(i, u);
int dist = d[i] + d[u] - 2 * d[l];
if(dist % 2 == 0 || j == 0){
n.pb({i, j});
if(u < i && j > 0){
k[l].pb({u, i, j});
}
}
}
graf[u] = n;
}
int rec(int u, int pp, int x, pi &dz){
if(u == x){
if(dz.ft == -1) dz.ft = pp;
else dz.sc = pp;
return 0;
}
int idx = N - 1, t = -1;
for(auto [i,j] : graf[u]){
t++;
if(i == p[u] || j > 0) continue;
if(i == pp) idx -= (1 << t);
}
return dp[u][idx] - dp[pp][N - 1] + rec(p[u], u, x, dz);
}
void solve(int u, int v){
for(auto [i, j] : graf[u]){
if(j > 0 || i == v) continue;
solve(i, u);
}
for(int i = 0; i < N; i++){
int t = -1;
for(auto [x, j] : graf[u]){
t++;
if(x == v || j > 0) continue;
dp[u][i] += dp[x][N - 1];
}
}
for(auto [a, b, val] : k[u]){
pi dz = {-1, -1};
int idx = 0, w = rec(a, -1, u, dz) + rec(b, -1, u, dz), t = -1, odj = 0;
for(auto [i, j] : graf[u]){
t++;
if(i == v || j > 0) continue;
if(i == dz.ft || i == dz.sc){
idx += (1 << t);
odj += dp[i][N - 1];
}
}
for(int i = 0; i < N; i++){
if((i & idx) == idx){
dp[u][i] = max(dp[u][i], dp[u][i ^ idx] + val - odj + w);
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n >> m;
int s = 0;
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
graf[a].pb({b, c});
graf[b].pb({a, c});
s += c;
}
dfs(1, 1);
for(int i = 1; i <= n; i++) fix(i);
solve(1, 1);
int ans = 0;
for(int i = 0; i < N; i++) ans = max(ans, dp[1][i]);
cout << s - ans << "\n";
return 0;
}
