#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define compact(x) (x).erase(unique(all(x)),(x).end())
#define pb(x) push_back(x)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int inf = 1e9;
const ll linf = 1e18;
const double pi = acos(-1);
const int N = 1005;
const int M = 5005;
const int K = 10;
const int LOG = 31 - __builtin_clz(N) + 1;
struct edge{
int u,v,w;
edge(){}
edge(int a,int b,int c){
u = a, v = b, w = c;
}
};
int dp[N][1 << K];
int sum[N][N];
int pa[N][LOG];
int h[N];
int n,m;
vector<int> a[N];
vector<edge> e;
vector<int> f[N];
vector<pii> g[N];
int lca(int u,int v){
if (h[u] < h[v]) swap(u,v);
int k = h[u] - h[v];
for (int i = 0; i < LOG; i++){
if (k & (1 << i)) u = pa[u][i];
}
if (u == v) return u;
for (int i = LOG - 1; i >= 0; i--){
if (pa[u][i] == pa[v][i]) continue;
u = pa[u][i];
v = pa[v][i];
}
return pa[u][0];
}
int getId(int u,int v){
///u is an ancestor of v
int k = h[v] - h[u] - 1;
for (int i = 0; i < LOG; i++){
if (k & (1 << i)) v = pa[v][i];
}
for (int i = 0; i < a[u].size(); i++){
int nxt = a[u][i];
if (nxt == v) return i;
}
return -1;
}
void preDfs(int u,int p = -1){
for (int i = 1; (1 << i) <= h[u]; i++){
pa[u][i] = pa[pa[u][i - 1]][i - 1];
}
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i];
if (v == p){
a[u].erase(a[u].begin() + i);
i--;
continue;
}
h[v] = h[u] + 1;
pa[v][0] = u;
preDfs(v,u);
}
}
int full(int u){
return (1 << int(a[u].size())) - 1;
}
int dfs(int u,int mask);
int lift1(int v,int fin){
if (v == fin) return 0;
int res = dfs(v,full(v));
int u = -1;
while(1){
int u = pa[v][0];
if (u == fin) break;
int id = 0;
for (id; id < a[u].size(); id++){
if (a[u][id] == v) break;
}
res += dfs(u, full(u) ^ (1 << id));
v = u;
}
return res;
}
int lift(int v,int fin){
return sum[fin][v];
}
bool valid(int id,int mask){
if (id == -1) return 1;
return (mask & (1 << id)) ? 1 : 0;
}
void cal(int x,int u){
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i];
sum[x][v] = dfs(v,full(v));
sum[x][v] += sum[x][u];
sum[x][v] -= dfs(u,full(u));
sum[x][v] += dfs(u,full(u) ^ (1 << i));
cal(x,v);
}
}
int dfs(int u,int mask){
if (dp[u][mask] != -1) return dp[u][mask];
int& res = dp[u][mask];
res = 0;
///not take
for (int i = 0; i < a[u].size(); i++){
if (!(mask & (1 << i))) continue;
int v = a[u][i];
res += dfs(v,full(v));
}
///take
sum[u][u] = 0;
for (int i = 0; i < a[u].size(); i++){
if (!(mask & (1 << i))) continue;
int v = a[u][i];
sum[u][v] = dfs(v,full(v));
// res += sum[u][v];
cal(u,v);
}
for (int i = 0; i < f[u].size(); i++){
int id = f[u][i];
int sum = e[id].w;
int l = e[id].u;
int x = g[u][i].fi;
int r = e[id].v;
int y = g[u][i].se;
if ((!valid(x,mask)) || (!valid(y,mask))) continue;
// assert(lift1(l,u) == lift(l,u));
// assert(lift1(r,u) == lift(r,u));
sum += lift(l,u) + lift(r,u);
int newmask = mask;
if (x != -1) newmask ^= (1 << x);
if (y != -1) newmask ^= (1 << y);
sum += dfs(u,newmask);
res = max(res, sum);
}
return res;
}
signed main(){
cin.tie(0) -> sync_with_stdio(0);
#define TEXT "training"
if (fopen(TEXT".inp","r")){
freopen(TEXT".inp","r",stdin);
// freopen(TEXT".out","w",stdout);
}
cin >> n >> m;
for (int i = 1; i <= m; i++){
int u,v,w;
cin >> u >> v >> w;
if (w == 0){
a[u].push_back(v);
a[v].push_back(u);
}
else e.push_back(edge(u,v,w));
}
preDfs(1);
int res = 0;
int total = 0;
for (int i = 0; i < e.size(); i++){
int u = e[i].u;
int v = e[i].v;
int w = e[i].w;
if ((h[u] + h[v]) & 1) res += w;
else{
total += w;
int l = lca(u,v);
f[l].push_back(i);
int x = getId(l,u);
int y = getId(l,v);
// cout << u << " " << v << " " << l << " " << x << " " << y << "\n";
g[l].push_back(pii(x,y));
}
}
memset(dp,-1,sizeof(dp));
int tmp = dfs(1,full(1));
// cout << total << "\n";
// cout << tmp << "\n";
res += total - tmp;
cout << res << "\n";
return 0;
}
