#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define fr first
#define sc second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main() {
cin.tie(0)->sync_with_stdio(0);
// freopen("diamond.in", "r", stdin);
// freopen("diamond.out", "w", stdout);
ll n,m; cin >> n >> m;
vector<vector<ll>> graph(n);
// {a,b,c}
vector<tuple<ll,ll,ll>> unpaved;
rep(i,0,m) {
ll a,b,c; cin >> a >> b >> c;
a--;b--;
if (c != 0) unpaved.pb({a,b,c});
else {
graph[a].pb(b);
graph[b].pb(a);
}
}
vector<ll> rank(n);
vector<pair<ll,ll>> par(n,{-1ll,-1ll});
vector<vector<ll>> child(n);
vector<ll> dfsorder;
auto dfs = [&](const auto &self, ll cur, ll crank, ll cpar, ll cpari) -> void {
dfsorder.pb(cur);
rank[cur] = crank;
par[cur] = {cpar, cpari};
for(auto nxt : graph[cur]) if (nxt != cpar) child[cur].pb(nxt);
rep(i,0,sz(child[cur])) {
self(self,child[cur][i], crank + 1, cur, i);
}
};
dfs(dfs, 0, 0, -1, -1);
reverse(all(dfsorder));
// cout << "GRAPH" << endl;
rep(i,0,0) {
cout << i << " - ";
cout << rank[i] << " - ";
cout << "(" << par[i].fr << ", " << par[i].sc << ") - ";
for(auto nxt : child[i]) cout << nxt << ' ';
cout << endl;
}
// node, index into child of cur
vector<vector<pair<ll,ll>>> subchild(n);
vector<vector<ll>> subtoi(n, vector<ll>(n, -1));
rep(i,0,n) {
ll cur = i;
while(cur != 0) {
subchild[par[cur].fr].pb({i,par[cur].sc});
subtoi[par[cur].fr][i] = par[cur].sc;
cur = par[cur].fr;
}
}
// cout << "SUBCHILD" << endl;
rep(i,0,0) {
cout << i << " - ";
for(auto [a,b] : subchild[i]) cout << a << "," << b << " ";
cout << endl;
}
// IF UNPAVED STARTS FOR CURNODE, INGORE THAT END
// {a, b, c}
vector<vector<tuple<ll,ll,ll>>> unp(n);
ll cnst = 0;
for(auto [a,b,c] : unpaved) {
cnst += c;
if ((rank[a] + rank[b]) % 2 != 0) continue;
ll aa = a, bb = b;
while(rank[aa] > rank[bb]) aa = par[aa].fr;
while(rank[bb] > rank[aa]) bb = par[bb].fr;
while(aa != bb) aa = par[aa].fr, bb = par[bb].fr;
unp[bb].pb({a,b,c});
}
// cout << "UNP" << endl;
// cout << cnst << endl;
rep(i,0,0) {
cout << i << " - ";
for(auto [a,b,c] : unp[i]) {
cout << a << ", " << b << ", " << c << " | ";
}
cout << endl;
}
vector<vector<ll>> dp(n, vector<ll>(n, 0ll));
for(auto cur : dfsorder) {
if (sz(child[cur]) == 0) continue;
ll nc = sz(child[cur]);
vector<ll> sums(1ll << nc, 0ll);
rep(mask, 1, 1ll << nc) {
ll i = __builtin_ctz(mask);
ll nxt = child[cur][i];
sums[mask] = dp[nxt][nxt] + sums[mask ^ (1 << i)];
}
vector<ll> masks(1ll << nc, 0ll);
rep(mask, 1, 1ll << nc) {
masks[mask] = sums[mask];
for(auto [a,b,c] : unp[cur]) {
ll add = 0;
ll ai = subtoi[cur][a];
ll bi = subtoi[cur][b];
// think
if (a != cur and !(1 & (mask >> ai))) continue;
if (b != cur and !(1 & (mask >> bi))) continue;
ll submask = mask;
if (ai != -1) add += dp[child[cur][ai]][a], submask ^= 1ll << ai;
if (bi != -1) add += dp[child[cur][bi]][b], submask ^= 1ll << bi;
masks[mask] = max(masks[mask], masks[submask] + c + add);
}
}
dp[cur][cur] = masks[(1 << nc) - 1];
for(auto [node, i] : subchild[cur]) {
dp[cur][node] = masks[((1 << nc) - 1) ^ (1ll << i)] + dp[child[cur][i]][node];
}
}
cout << cnst - dp[0][0] << '\n';
}
