#pragma GCC optimize("O5,unroll-loops,inline,fast-math") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) #define int long long using namespace std; int n,m,eu[5005],ev[5005],ec[5005],lca[5005],adj[1005][15],deg[1005],d[1005],p[1005],t[1005],ft[1005],par[1005],cm[1005],num[1005],dp[1005][1024],vis[1005],s[1005],sum=0,top=0,ti=0,idx[5005],pmask[1005]; signed main(void) { exoworldgd; cin >> n >> m, memset(deg,0,sizeof(deg)), memset(dp,0,sizeof(dp)), memset(num,0,sizeof(num)),memset(vis,0,sizeof(vis)), iota(idx,idx+m,0); for (int i = 0; i < m; i++) cin >> eu[i] >> ev[i] >> ec[i], eu[i]--, ev[i]--, !ec[i] ? adj[eu[i]][deg[eu[i]]++]=ev[i], adj[ev[i]][deg[ev[i]]++]=eu[i] : sum+=ec[i]; s[top++]=0, par[0]=-1, d[0]=0, p[0]=0, cm[0]=0, pmask[0]=0; while (top > 0) { int u = s[top-1],id; if (!vis[u]) { vis[u] = 1,id=0, t[u]=ti++; for (int i = 0; i < deg[u]; i++) { int v = adj[u][i]; if (par[u] == v) continue; par[v] = u, d[v]=d[u]+1, p[v]=p[u]^1, pmask[v]=1<<id, cm[v]=1<<id++, s[top++]=v; } } else ft[u]=ti++, top--; } for (int i = 0; i < m; i++) { int u=eu[i], v=ev[i]; while (d[u] > d[v]) u=par[u]; while (d[v] > d[u]) v=par[v]; while (u^v) u = par[u], v = par[v]; lca[i] = u; } sort(idx,idx+m,[&](int a, int b) {return ft[lca[a]] < ft[lca[b]];}); for (int i = 0; i < m; i++) { if (ec[idx[i]]&&(p[eu[idx[i]]]^p[ev[idx[i]]])) continue; int l=lca[idx[i]], c=ec[idx[i]],um=0,vm=0; for(int curr=eu[idx[i]],mask=0; curr!=l; c+=dp[curr][mask],mask=pmask[curr],um=mask,curr=par[curr]); for(int curr=ev[idx[i]],mask=0;curr!=l;c+=dp[curr][mask],mask=pmask[curr],vm=mask,curr=par[curr]); for (int j = (1<<deg[l])-1; j >= 0; j--) if (!(j&um)&&!(j&vm)) dp[l][j]=max(dp[l][j],dp[l][j|um|vm]+c); } cout << sum-dp[0][0]; }