#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int N = 1005;
const int inf = 1e15;
const long long mod = 998244353;
const long long p2 = 31;
int n, m;
vector<int> g[N];
int d[N], cnt[N], pos[N], pa[N][12];
struct Bridge {
int a, b, w;
};
vector<Bridge> store[N];
vector<pair<pair<int, int>, int>> E;
int dp[N][1 << 11];
void dfs(int u, int p, int cur_d) {
pa[u][0] = p;
d[u] = cur_d;
for (int v : g[u]) if (v != p) {
pos[v] = cnt[u];
cnt[u] ++;
dfs(v, u, cur_d + 1);
}
}
void lca_process(int a, int b, int w) {
if (d[a] % 2 != d[b] % 2) return;
if (d[a] > d[b]) swap(a, b);
int u = a, v = b;
int k = d[v] - d[u];
for (int i = 11; i >= 0; i --) {
if ((k >> i) & 1) v = pa[v][i];
}
if (u == v) {
store[u].push_back({b, b, w});
return;
}
for (int i = 11; i >= 0; i --) {
if (pa[u][i] != pa[v][i]) {
u = pa[u][i];
v = pa[v][i];
}
}
store[pa[u][0]].push_back({a, b, w});
}
void prep() {
dfs(1, 1, 0);
for (int k = 1; k < 12; k ++) {
for (int i = 1; i <= n; i ++) {
pa[i][k] = pa[pa[i][k - 1]][k - 1];
}
}
for (auto e : E) {
lca_process(e.fi.fi, e.fi.se, e.se);
}
}
void DFS(int u, int p) {
int best[cnt[u]][cnt[u]];
for (int i = 0; i < cnt[u]; i ++) {
for (int j = 0; j < cnt[u]; j ++) {
best[i][j] = 0;
}
}
for (int v : g[u]) if (v != p) {
DFS(v, u);
best[pos[v]][pos[v]] = dp[v][(1 << cnt[v]) - 1];
}
for (Bridge br : store[u]) {
//cout << u << " : " << br.a << " - " << br.b << " , " << br.w << "\n";
int a = br.a;
int sum = 0;
sum = dp[a][(1 << cnt[a]) - 1];
while (true) {
int p = pa[a][0];
sum += dp[p][(1 << cnt[p]) - 1 - (1 << pos[a])];
if (p == u) {
break;
}
a = p;
}
if (br.a == br.b) {
best[pos[a]][pos[a]] = max(best[pos[a]][pos[a]], sum + br.w);
}
else {
int b = br.b;
sum += dp[b][(1 << cnt[b]) - 1];
while (true) {
int p = pa[b][0];
sum += dp[p][(1 << cnt[p]) - 1 - (1 << pos[b])];
if (p == u) break;
b = p;
}
best[pos[b]][pos[a]] = best[pos[a]][pos[b]] = max(best[pos[a]][pos[b]], sum + br.w);
}
}
for (int mask = 1; mask < (1 << cnt[u]); mask ++) {
int i = cnt[u] - 1;
while (((mask >> i) & 1) == 0) i --;
for (int t = 0; t <= i; t ++) {
if ((mask >> t) & 1) {
dp[u][mask] = max(dp[u][mask], dp[u][mask - (1 << t)] + best[t][t]);
dp[u][mask] = max(dp[u][mask], dp[u][mask - (1 << t) - (1 << i)] + best[i][t]);
}
}
}
//cout << u << " " << dp[u][(1 << cnt[u]) - 1] << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
int sum = 0;
int a, b, c;
for (int i = 1; i <= m; i ++) {
cin >> a >> b >> c;
if (c == 0) {
g[a].push_back(b);
g[b].push_back(a);
} else {
E.push_back({{a, b}, c});
sum += c;
}
}
prep();
DFS(1, 1);
cout << sum - dp[1][(1 << cnt[1]) - 1];
return 0;
}
