#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
const int P = 10;
const int M = (1<<P);
int Solution[N][M];
vector<int> Graph[N];
pair<int, int> Parents[N];
int Depth[N];
vector<tuple<int, int, int>> Edges;
vector<tuple<int, int, int>> Check[N];
void DFS1(int u, int parent, int idx)
{
Parents[u] = {parent, idx};
Depth[u] = Depth[parent] + 1;
for(int i = 0; i < Graph[u].size(); i++) {
int v = Graph[u][i];
if(v != parent)
DFS1(v, u, i);
}
}
void Fix()
{
for(auto [a, b, c] : Edges) {
if(c == 0 || (Depth[a] % 2 != Depth[b] % 2))
continue;
int u = a, v = b;
if(Depth[u] > Depth[v])
swap(u, v);
while(Depth[u] != Depth[v])
v = Parents[v].first;
while(u != v) {
u = Parents[u].first;
v = Parents[v].first;
}
Check[u].push_back({a, b, c});
}
}
pair<int, int> Find(int u, int idx, int limit)
{
if(u == limit)
return {0, idx};
int val = 0;
if(idx != -1)
Solution[u][(M-1) ^ (1<<idx)];
else
val = Solution[u][M-1];
pair<int, int> sol = Find(Parents[u].first, Parents[u].second, limit);
return {sol.first + val, sol.second};
}
void DFS2(int u)
{
for(auto v : Graph[u]) {
if(v != Parents[u].first)
DFS2(v);
}
for(int i = 0; i < Graph[u].size(); i++) {
int add = Solution[Graph[u][i]][M-1];
for(int j = 0; j < M; j++) {
if(j & (1<<i))
Solution[u][j] = max(Solution[u][j], Solution[u][j ^ (1<<i)] + add);
}
}
for(auto [a, b, c] : Check[u]) {
pair<int, int> x = Find(a, -1, u);
pair<int, int> y = Find(b, -1, u);
int cost = x.first + y.first + c;
int mask = 0;
if(x.second != -1)
mask |= (1<<(x.second));
if(y.second != -1)
mask |= (1<<(y.second));
for(int j = 0; j < M; j++) {
if((j & mask) == mask)
Solution[u][j] = max(Solution[u][j], Solution[u][j ^ mask] + cost);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, a, b, c;
cin >> n >> m;
int sum = 0;
for(int i = 0; i < m; i++) {
cin >> a >> b >> c;
if(c == 0) {
Graph[a].push_back(b);
Graph[b].push_back(a);
}
Edges.push_back({a, b, c});
sum += c;
}
DFS1(2, 0, 0);
Fix();
DFS2(2);
cout << (sum - Solution[2][M-1]) << "\n";
return 0;
}
