// Src : Vux2Code
/* Note :
Toibingu
*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
const ll maxN = 5e3 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;
ll bit (ll x, ll y) {return (x >> y) & 1;}
void maxi (ll &x, ll y) {x = max (x, y);}
void mini (ll &x, ll y) {x = min (x, y);}
ll t = 1;
struct Edge {ll u, v, w, lca;};
ll n, m, dis [maxN], st [maxN], en [maxN], child [maxN], cnt, sum, f [maxN] [1 << 10], cost;
pll par [maxN], tmpU, tmpV;
vector <ll> adj [maxN];
vector <Edge> edge;
void dfs (ll x = 1, ll pr = 0) {
dis [x] = !dis [pr];
st [x] = ++ cnt;
for (ll i : adj [x]) if (i != pr) {
dfs (i, x);
par [i] = {x, 1 << child [x] ++};
}
en [x] = ++ cnt;
}
bool ckChild (ll x, ll y) {
return st [x] <= st [y] && en [y] <= en [x];
}
ll lca (ll x, ll y) {
while (!ckChild (x, y)) x = par [x]. fi;
return x;
}
void solve () {
cin >> n >> m;
for (int i = 1, u, v, w; i <= m; i ++) {
cin >> u >> v >> w;
if (!w) {
adj [u]. push_back (v);
adj [v]. push_back (u);
}
cost += w;
edge. push_back ({u, v, w});
}
dfs ();
// cerr << "Check1 \n";
for (Edge &i : edge) i. lca = lca (i. u, i. v);
sort (edge. begin (), edge. end (), [&] (Edge x, Edge y) {return en [x. lca] < en [y. lca];});
// cerr << "Check2 \n";
for (Edge i : edge) {
if (i. w && (dis [i. u] ^ dis [i. v])) continue;
sum = i. w;
for (tmpU = {i. u, 0}; tmpU. fi != i. lca; tmpU = par [tmpU. fi]) sum += f [tmpU. fi] [tmpU. se];
for (tmpV = {i. v, 0}; tmpV. fi != i. lca; tmpV = par [tmpV. fi]) sum += f [tmpV. fi] [tmpV. se];
// cerr << sum << '\n';
for (int j = (1 << child [i. lca]) - 1; ~j; j --) {
if (!((j & tmpU. se) || (j & tmpV. se))) {
maxi (f [i. lca] [j], sum + f [i. lca] [j | tmpU. se | tmpV. se]);
}
}
}
// cerr << cost << ' ' << f [1] [0];
// cerr << "Check3\n";
cout << cost - f [1] [0];
}
int main () {
ios::sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
// #define TASK "E:/Code/CP/task"
// if (fopen (TASK".inp", "r")) {
// freopen (TASK".inp", "r", stdin);
// freopen (TASK".out", "w", stdout);
// }
//cin >> t;
while (t--) solve ();
}
