#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e3 + 1, M = 5e3 + 1, INF = 1e9;
const ll mod = 1e9 + 7;
int n, m, cost[M], tin[N], tout[N], cash[M], timer;
int h[N], parent[N], dp[(1 << 10)][N], rc[N][N];
pair<int, int> road[M];
vector< int > g[N], ch[N], maybe[N];
void dfs(int v, int pr){
parent[v] = pr, tin[v] = ++timer;
int j = 0;
for(int to: g[v]){
if(to != pr){
h[to] = h[v] + 1, ch[v].push_back(to), rc[v][to] = j++;
dfs(to, v);
}
}
tout[v] = ++timer;
}
bool check(int x, int y){
return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}
int solve(int v, int mask){
if(dp[v][mask] != -1)
return dp[v][mask];
int &res = dp[v][mask];
res = 0;
for(int i = 0;i < ch[v].size();i++){
if((mask >> i) & 1)
continue;
res += solve(ch[v][i], 0);
}
for(int id: maybe[v]){
int x = road[id].X, y = road[id].Y, newmask = mask, opt = 0;
for(int i = 0;i < ch[v].size();i++){
if(check(ch[v][i], y))
swap(x, y);
if(check(ch[v][i], x)){
newmask ^= (1 << i);
if(cash[id] == -1){
int tmp = parent[x], last = x;
while(tmp != v){
opt += solve(tmp, 1 << (rc[tmp][last]));
last = tmp, tmp = parent[tmp];
}
opt += solve(x, 0);
}
}
}
if(cash[id] == -1)
cash[id] = opt;
if((newmask & mask) != mask)
continue;
opt = solve(v, newmask) + cost[id] + cash[id];
res = max(res, opt);
}
return res;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof(dp)), memset(cash, -1, sizeof(cash));
cin >> n >> m;
for(int i = 1, x, y;i <= m;i++){
cin >> x >> y >> cost[i], road[i] = MP(x, y);
if(!cost[i])
g[x].push_back(y), g[y].push_back(x);
}
dfs(1, 1);
int all = 0;
for(int i = 1;i <= m;i++){
if(!cost[i])
continue;
all += cost[i];
int x = road[i].X, y = road[i].Y;
if((h[x] + h[y]) & 1)
continue;
// cerr << x << " " << y << "\n";
while(x != y){
if(h[x] < h[y])
swap(x, y);
x = parent[x];
}
maybe[x].push_back(i);
}
solve(1, 0);
cout << all - dp[1][0];
}
