#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 = (1e+3)+9;
const int mod = 998244353;
struct sc
{
int a , b;
int c;
};
int N ,M ;
vector <int> t[maxn];
vector <int> addi[maxn];
vector <sc> V;
vector <sc> Vreal;
ll sum = 0;
int dep[maxn];
vector <int> kol; //sciezka
ll dp[maxn]; //sciezka
int kt[maxn] ; // sciezka
void DFSdep(int v, int o)
{
kol.push_back(v);
dep[v] = dep[o]+1;
for(auto p : t[v])
{
if(p == o)continue;;
DFSdep(p,v);
}
for(auto p : addi[v])
{
if(V[p].b == v)continue;
if(abs(dep[v] - dep[V[p].b])%2)
{
sum += V[p].c;
}
else
{
Vreal.push_back(V[p]);
}
}
}
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;
addi[a].push_back(V.size());
addi[b].push_back(V.size());
V.push_back(temp);
}
}
int S = 0;
for(int i = 1 ; i <= N ; i++)
{
if(t[i].size() == 1)S = i;
}
dep[0] = 0;
DFSdep(S,0);
V = Vreal;
for(int i = 1; i <= N ; i++)addi[i].clear();
for(int i = 0; i < V.size() ; i++)
{
if(dep[V[i].a] > dep[V[i].b])swap(V[i].a , V[i].b);
addi[V[i].b].push_back(i);
sum += V[i].c;
}
for(int i = 0; i < kol.size() ; i++)
{
kt[kol[i]] = i;
}
dp[0] = 0;
for(int i = 1; i < kol.size() ; i++)
{
dp[i] = dp[i-1];
for(auto p : addi[kol[i]])
{
dp[i] = max(dp[i] , (dp[kt[V[p].a]] + V[p].c));
}
}
cout << sum - dp[N-1] << '\n';
return 0;
}
