// 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 = 2e3 + 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], cid[N];
long long dp[N][N], sum, mx[N];
vector<int> adj[N];
vector<array<int, 3>> edges, query[N];
void dfs1(int c, int p)
{
par[c] = p;
int id = -1;
for (int i : adj[c])
{
id++;
if (i == p)
continue;
cid[i] = id;
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);
}
int s = adj[c].size();
for (auto [a, b, v] : query[c])
{
long long cur = 0;
if (a != c)
cur += mx[a];
if (b != c)
cur += mx[b];
while (par[a] != c && a != c)
{
// cout << a << " " << (((1 << adj[par[a]].size()) - 1) ^ (1 << cid[a])) << "\n";
cur += dp[par[a]][((1 << adj[par[a]].size()) - 1) ^ (1 << cid[a])];
a = par[a];
}
while (par[b] != c && b != c)
{
// cout << b << "\n";
cur += dp[par[b]][((1 << adj[par[b]].size()) - 1) ^ (1 << cid[b])];
b = par[b];
}
int i1 = s, i2 = s;
for (int id = 0; id < s; id++)
{
int &i = adj[c][id];
if (i == a)
{
i1 = id;
}
if (i == b)
{
i2 = id;
}
}
cur += v;
// cout << cur << " " << a << " " << b << " " << c << "\n";
for (int x = 0; x < (1 << s); x++)
{
mx[c] = max(dp[c][x], mx[c]);
}
for (int x = (1 << s) - 1; x >= 0; 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);
dp[c][m] = max(dp[c][m], dp[c][x] + cur);
}
}
for (int x = 0; x < s; x++)
{
if (adj[c][x] == p)
continue;
for (int y = 0; y < (1 << s); y++)
{
if (y >> x & 1)
continue;
dp[c][y ^ (1 << x)] = max(dp[c][y ^ (1 << x)], dp[c][y] + mx[adj[c][x]]);
}
}
for (int x = 0; x < (1 << s); x++)
{
long long cur = dp[c][x];
for (int y = 0; y < s; y++)
{
if (adj[c][y] == p)
continue;
if (x >> y & 1)
continue;
cur += mx[adj[c][y]];
}
mx[c] = max(mx[c], cur);
// cout << dp[c][x] << " ";
}
// cout << "\n";
// cout << mx[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);
// cout << a << " " << b << "\n";
}
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)
{
// cout << a << " " << b << " " << c << "\n";
query[lca(a, b)].push_back({a, b, c});
}
}
dfs2(1, 0);
cout << sum - mx[1] << "\n";
}
signed main()
{
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;
}
