#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const int oo = (1e+9)+9;
const int base = (1<<19);
const int maxn = 7*(1e+3)+9;
const int mod = 998244353;
struct sc
{
int a , b;
int c;
};
int S = 0;
int N ,M ;
vector <int> t[maxn];
vector <int> s[maxn];
vector <sc> V;
vector <sc> Vreal; // chwilowe
ll sum = 0;
int dep[maxn];
int ktuo[maxn];
int dp[maxn][1 << 10];
int lca[maxn]; //lca dla danej pary o indeksie i
vector<pii> podddsc[maxn]; // poddrzewa dla danej sciezki o indeksie i , {poddrzewo , ktore sciezkie usuiete}
int mskall[maxn]; //maska gdy wszyscy synowie sa ok
vector <int> sclca[maxn]; // sciezkie ktorych lca to i
int sumsc[maxn]; // suma wartosci dp poddrzew sciezki poza lca
int PC[maxn]; // ktore sciezki z lca sa zajete przez dana sciezke
int szu = -1;
bool DFSdis(int v ,int o , int dis)
{
if(szu == v)
{
return (dis%2);
}
bool czy = 0;
for(auto p : t[v])
{
if(p == o)continue;
czy |= DFSdis(p,v,dis+1);
}
return czy;
}
void DFSdep(int v, int o)
{
dep[v] = dep[o]+1;
for(auto p : t[v])
{
if(p == o)continue;;
ktuo[p] = s[v].size();
s[v].push_back(p);
DFSdep(p,v);
}
}
int asc = -1 , bsc = -1 , aktind = -1;
int DFSsc(int v)
{
int sumloc = 0;
if(v == asc)sumloc++;
if(v == bsc)sumloc++;
int a1 = -1 , a2 = -1;
mskall[v] = (1<< (s[v].size()))-1;
for(auto p : s[v])
{
int temp = DFSsc(p);
if(temp)
{
if(a1 == -1)a1 = p;
else a2 = p;
}
sumloc += temp;
}
if(sumloc != 0)
{
if(a1 == -1)podddsc[aktind].push_back({v , mskall[v]});
else if(a2 == -1)podddsc[aktind].push_back({v , mskall[v]^(1 << ktuo[a1])});
else podddsc[aktind].push_back({v , mskall[v]^(1 << ktuo[a1])^(1 << ktuo[a2])});
}
if(sumloc == 2)
{
lca[aktind] = v;
if(a2 != -1)PC[aktind] = (1 << ktuo[a1])^(1 << ktuo[a2]);
else PC[aktind] = (1 << ktuo[a1]);
sumloc = 0;
}
return sumloc;
}
void scpre()
{
for(int i = 0; i < V.size() ; i++)
{
asc = V[i].a;
bsc = V[i].b;
aktind = i;
DFSsc(S);
sclca[lca[i]].push_back(i);
}
}
void DFS(int v)
{
int sumloc = 0;
for(auto p : s[v])
{
DFS(p);
sumloc += dp[p][mskall[p]];
}
for(auto i : sclca[v])
{
for(auto p : podddsc[i])
{
if(p.st != v)sumsc[i] += dp[p.st][p.nd];
}
}
dp[v][0] = 0;
for(int j = 1; j <= mskall[v] ; j++)
{
sumloc = 0;
for(int i = 0; i < s[v].size() ; i++)
{
if((j&(1<<i)))sumloc += dp[s[v][i]][mskall[s[v][i]]];
}
dp[v][j] = sumloc;
dp[v][j] = max(dp[v][j] , dp[v][(j^((j^(-j))))]);
for(auto i : sclca[v])
{
if((j&PC[i]) != PC[i])continue;
dp[v][j] = max(dp[v][j] , sumsc[i] + dp[v][(j^PC[i])] + V[i].c);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
int a , b , c;
for(int i = 0 ;i < M ; i++)
{
cin >> a >> b >> c;
if(c == 0)
{
t[a].push_back(b);
t[b].push_back(a);
}
else
{
sc temp;
temp.a = a;
temp.b = b;
temp.c = c;
V.push_back(temp);
}
}
for(auto f : V)
{
szu = f.b;
if(DFSdis(f.a , 0 , 0))
{
sum += f.c;
}
else
{
Vreal.push_back(f);
}
}
for(int i = 1 ; i <= N ; i++)
{
if(t[i].size() == 1)S = i;
}
dep[0] = 0;
DFSdep(S,0);
V = Vreal;
scpre();
/*
cout << "S: \n";
for(int i = 1; i <= N ; i++)
{
cout << " " << i << ' '; for(auto p : s[i])cout << p << ' ';
cout << '\n';
}
cout << "SCIEZKI: \n";
for(int i = 0 ; i < V.size() ; i++)
{
cout << " " << i << ": \n";
cout << " " << V[i].a << ' ' << V[i].b << ' ' << lca[i] << " " << PC[i] << '\n';
cout << " " << V[i].c << '\n';
cerr << " PODD: \n";
for(auto p : podddsc[i])
{
cout << " " << p.st << ' ' << p.nd << '\n';
}
cout << "END\n";
}
cerr << sum << '\n';*/
for(int i =0 ; i < V.size() ; i++)
{
auto p = V[i];
}
for(auto p : V)sum += p.c;
DFS(S);
cout << sum-dp[S][mskall[S]] << '\n';
return 0;
}
