// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 5e3 + 5;
const int M = 5e4 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e18 + 5;
const int B = 400;
const int MOD = 1e9;
int n, m, depth[N], binlift[LG][N], par[N];
long long dp[N], sum;
vector<int> adj[N];
vector<array<int, 3>> edges, query[N];
void dfs1(int c, int p)
{
par[c] = p;
for (int i : adj[c])
{
if (i == p)
continue;
depth[i] = depth[c] + 1;
binlift[0][i] = c;
for (int x = 1; x < LG; x++)
{
binlift[x][i] = binlift[x - 1][binlift[x - 1][i]];
}
dfs1(i, c);
}
}
int lca(int a, int b)
{
if (depth[a] != depth[b])
{
if (depth[a] < depth[b])
swap(a, b);
for (int x = 0; x < LG; x++)
{
if ((depth[a] - depth[b]) >> x & 1)
{
a = binlift[x][a];
}
}
}
if (a == b)
return a;
for (int x = LG - 1; x >= 0; x--)
{
if (binlift[x][a] != binlift[x][b])
{
a = binlift[x][a];
b = binlift[x][b];
}
}
return binlift[0][a];
}
void dfs2(int c, int p)
{
for (int i : adj[c])
{
if (i == p)
continue;
dfs2(i, c);
dp[c] += dp[i];
}
int s = adj[c].size();
long long mask[1 << s];
memset(mask, 0, sizeof(mask));
for (auto &[a, b, v] : query[c])
{
long long cur = 0;
if (a != c)
cur += dp[a];
if (b != c)
cur += dp[b];
while (par[a] != c && a != c)
{
for (int i : adj[par[a]])
{
if (i != a && i != par[par[a]])
{
cur += dp[i];
}
}
if (par[a] == c)
break;
a = par[a];
}
while (par[b] != c && b != c)
{
for (int i : adj[par[b]])
{
if (i != b && i != par[par[b]])
{
cur += dp[i];
}
}
b = par[b];
}
int i1 = s, i2 = s, id = 0;
for (int i : adj[c])
{
if (i == p)
{
id++;
continue;
}
if (i == a)
{
i1 = id;
id++;
continue;
}
if (i == b)
{
i2 = id;
id++;
continue;
}
id++;
cur += dp[i];
}
cur += v;
for (int x = 0; x < (1 << s); x++)
{
if ((x >> i1 & 1) && i1 != s)
continue;
if ((x >> i2 & 1) && i2 != s)
continue;
int m = x;
if (i1 != s)
m |= (1 << i1);
if (i2 != s)
m |= (1 << i2);
mask[m] = max(mask[m], mask[x] + cur);
}
}
for (int id = 0; id < s; id++)
{
int &i = adj[c][id];
if (i == p)
continue;
for (int x = 0; x < (1 << s); x++)
{
if (x >> id & 1)
continue;
mask[x] += dp[i];
}
id++;
}
for (int x = 0; x < (1 << s); x++)
{
dp[c] = max(mask[x], dp[c]);
}
// cout << dp[c] << " " << c << "dp\n";
}
void solve()
{
cin >> n >> m;
for (int x = 0; x < m; x++)
{
int a, b, c;
cin >> a >> b >> c;
if (c == 0)
{
adj[a].push_back(b);
adj[b].push_back(a);
}
else
{
sum += c;
edges.push_back({a, b, c});
}
}
dfs1(1, 0);
for (auto &[a, b, c] : edges)
{
if ((depth[a] + depth[b]) % 2 == 0)
{
query[lca(a, b)].push_back({a, b, c});
}
}
dfs2(1, 0);
cout << sum - dp[1] << "\n";
}
signed main()
{
// freopen("deleg.in", "r", stdin);
// freopen("deleg.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for (int x = 1; x <= t; x++)
{
solve();
}
return 0;
}
