#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>
struct edge {
int u, v, c, l, x, y; //x, y: the indices of the two sons of l on the path from l to u, v
};
int n, m, tot = 0;
const int MN = 1007, MM = 5007, MS = (1<<10)+7;
int dep[MN], fa[MN], jump[MN][11];
vi G[MN], g[MN];
vector<edge> b, a;
vector<edge> e_lca[MN]; //e_lca[i]: all edges with l as the lca of its two endpoints
int dp[MN][MS]; //dp[i][s]: for the subtree rooted at i, excluding all children nodes in s,
//the maximum total cost we can get by adding edges into the graph
int val[MN]; //val[v]: the precomputed value of sum of dps on a path from cur node to v
vi order[11];
int bits(int x) {return __builtin_popcount(x);}
void dfs(int node, int fat) {
fa[node] = fat;
dep[node] = dep[fat]+1;
for(int child : g[node]) {
if(child == fat) continue;
G[node].pb(child);
dfs(child, node);
}
}
pii lca(int u, int v) {
int j = 10;
if(dep[v] > dep[u]) swap(u, v);
for(int i = 0; i <= 10; i++) {
if((1<<i)&(dep[u]-dep[v])) u = jump[u][i];
}
if(u == v) return {u, u};
while(j >= 0) {
if(jump[u][j] != jump[v][j]) {
u = jump[u][j];
v = jump[v][j];
}
j--;
}
return {u, v};
}
void pushdown(int node, int fat, int v) {
val[node] += v;
for(int child : G[node]) {
if(child == fat) continue;
pushdown(child, node, v);
}
}
void dfsdp(int node, int fat) {
for(int child : G[node]) {
if(child == fat) continue;
dfsdp(child, node);
}
int sz = (int) G[node].size();
//not using any edges
for(int s = 0; s < 1<<sz; s++) {
for(int i = 0; i < sz; i++) {
if(((1<<i)&s)==0) {
dp[node][s] += dp[G[node][i]][0];
}
}
}
//using some edge
for(int s : order[sz]) {
for(edge e : e_lca[node]) {
// if(node == 1 && s == 0) {
// cout << e.u << ' ' << e.v << ' ' << e.x << ' ' << e.y << '\n';
// }
// if(node == 5) {
// cout << e.u << ' ' << e.v << ' ' << e.x << ' ' << e.y << '\n';
// }
if(e.x==-1 && e.y==-1) { //one of u, v is lca
// cout << "here" << '\n';
int ind = -1; //find index of son on the path from u to v
if(dep[e.u] < dep[e.v]) swap(e.u, e.v);
for(int i = 0; i < sz; i++) {
pii p = lca(e.u, G[node][i]);
if(p.fi==p.se) ind = i;
}
if((1<<ind)&s) continue;
dp[node][s] = max(dp[node][s], dp[node][s^(1<<ind)]+e.c+dp[e.u][0]+val[e.u]);
} else {
if((1<<e.x)&s || (1<<e.y)&s) continue;
dp[node][s] = max(dp[node][s], dp[node][s^(1<<e.x)^(1<<e.y)]+val[e.u]+val[e.v]+
e.c+dp[e.u][0]+dp[e.v][0]);
if(node == 1 && s == 0) {
// cout << dp[node][s^(1<<e.x)^(1<<e.y)] << ' ' << val[e.u] << ' ' << val[e.v] <<
// ' ' << e.c << ' ' << dp[e.u][0] << ' ' << dp[e.v][0] << '\n';
// cout << "cur: " << dp[node][s] << '\n';
}
}
// if(s == 0 && node == 1 && dp[1][0] == 40) {
// cout << "here: " << e.u << ' ' << e.v << '\n';
// }
}
}
//precompute val
for(int i = 0; i < sz; i++) {
pushdown(G[node][i], node, dp[node][1<<i]);
}
}
int cmp(int x, int y) {
return bits(x) > bits(y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y, z; cin >> x >> y >> z;
if(z == 0) g[x].pb(y), g[y].pb(x);
else b.pb({x, y, z, -1});
tot += z;
}
//lca precompute
dfs(1, 1);
for(int i = 1; i <= n; i++) jump[i][0] = fa[i];
for(int j = 1; j < 11; j++) {
for(int i = 1; i <= n; i++)
jump[i][j] = jump[jump[i][j-1]][j-1];
}
for(edge e : b) { // remove all edges that directly form even cycles
pii p = lca(e.u, e.v);
if(p.fi==p.se) e.l = p.fi;
else e.l = fa[p.fi];
// cout << e.u << ' ' << e.v << ' ' << e.l << '\n';
if((-2*dep[e.l]+dep[e.u]+dep[e.v]+1)%2==1) {
if(p.fi==p.se) e.x=e.y=-1;
for(int i = 0; i < G[e.l].size(); i++) {
if(G[e.l][i] == p.fi) e.x = i;
if(G[e.l][i] == p.se) e.y = i;
// cout << i << '\n';
}
a.pb(e);
e_lca[e.l].pb(e);
// cout << "pushed: " << e.u << ' ' << e.v << ' ' << e.x << ' ' << e.y << '\n';
}
// cout << e.u << ' ' << e.v << '\n';
} //precompute order to iterate masks
for(int sz = 1; sz <= 10; sz++) {
for(int s = 0; s < 1<<sz; s++) order[sz].pb(s);
sort(order[sz].begin(), order[sz].end(), cmp);
}
dfsdp(1, 0);
cout << tot-dp[1][0] << '\n';
// cout << dp[1][0] << '\n';
// cout << lca(7, 11).fi << '\n';
//
}
