/* ...... */
#include <bits/stdc++.h>
using namespace std;
#define inl inline
typedef long long ll;
typedef pair <int, int> pint;
#define all(p) begin (p), end (p)
#define empb emplace_back
using tint = tuple <int, int, int>;
constexpr int N = 1024, M = 5005;
int n, m, x, y, z, extm, fa[N], dep[N], sid[N];
vector <int> e[N]; tint ext[M];
vector <tint> ex[M]; int tot, f[N][1<<10];
inl void gomx (int &x, const int &y) { if (x < y) x = y; }
void dfs (int x, int fr) {
fa[x] = fr, dep[x] = dep[fr] + 1;
int scnt = 0;
for (const int y : e[x])
if (y != fr)
sid[y] = scnt++, dfs (y, x);
if (fr) e[x].erase (find (all (e[x]), fr));
}
inl int lca (int x, int y) {
static bool vis[N];
memset (vis, 0, n + 1);
while (x) vis[x] = 1, x = fa[x];
while (!vis[y]) y = fa[y];
return y;
}
inl pint cost (int l, int x) {
if (x == l) return { 0, 0 };
int res = f[x][0];
while (fa[x] != l)
res += f[fa[x]][1<<sid[x]], x = fa[x];
return { 1<<sid[x], res };
}
void dp (int x) {
vector <pint> lst; int id = 0;
for (const int y : e[x])
dp (y), lst.empb (1<<id++, f[y][0]);
for (const auto [u, v, w] : ex[x]) {
const auto [s1, c1] = cost (x, v);
const auto [s2, c2] = cost (x, u);
lst.empb (s1 | s2, c1 + c2 + w);
}
const int siz = e[x].size ();
memset (f[x], ~0x3f, 1<<12);
f[x][(1<<siz)-1] = 0;
for (const auto [msk, w] : lst)
for (int s = msk; s < 1<<siz; (++s) |= msk)
gomx (f[x][s^msk], f[x][s] + w);
}
int main () {
/* */
scanf ("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf ("%d%d%d", &x, &y, &z);
if (!z) e[x].empb (y), e[y].empb (x);
else ext[++extm] = { x, y, z }, tot += z;
}
dfs (1, 0);
for (int i = 1; i <= extm; ++i) {
tie (x, y, z) = ext[i];
if (dep[x] % 2 != dep[y] % 2);
else ex[lca (x, y)].empb (ext[i]);
}
dp (1); printf ("%d", tot - f[1][0]);
return 0;
}
