import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**6)
MOD = int(1e9+7)
MAXN = 5001
MAXK = 10
n, m, total_sum = 0, 0, 0
par = [(0, 0)] * MAXN
jump = [[0] * (MAXK + 1) for _ in range(MAXN)]
paths = [[] for _ in range(MAXN)]
deg = [0] * MAXN
order = [0] * MAXN
lvl = [0] * MAXN
ptr = 0
class Edge:
def __init__(self, a, b, c, lca):
self.a = a
self.b = b
self.c = c
self.lca = lca
def __lt__(self, other):
return order[self.lca] < order[other.lca]
edges = []
def dfs(pos=1, p=1):
global ptr
jump[pos][0] = p
for el in paths[pos]:
if el == p:
continue
lvl[el] = lvl[pos] + 1
par[el] = (pos, 1 << deg[pos])
deg[pos] += 1
dfs(el, pos)
order[pos] = ptr
ptr += 1
def LCA(a, b):
if lvl[a] < lvl[b]:
a, b = b, a
dist = lvl[a] - lvl[b]
for j in range(MAXK + 1):
if dist & (1 << j):
a = jump[a][j]
if a == b:
return a
for j in range(MAXK, -1, -1):
if jump[a][j] != jump[b][j]:
a = jump[a][j]
b = jump[b][j]
return jump[a][0]
dp = [[0] * (1 << MAXK) for _ in range(MAXN)]
def solve():
for edge in edges:
a, b, cur, lca = edge.a, edge.b, edge.c, edge.lca
if lvl[a] % 2 != lvl[b] % 2 and cur != 0:
continue
mask1, mask2 = 0, 0
while a != lca:
cur += dp[a][par[a][1]]
a, mask1 = par[a]
while b != lca:
cur += dp[b][par[b][1]]
b, mask2 = par[b]
mask1 |= mask2
for mask in range((1 << deg[lca]) - 1, -1, -1):
if mask & mask1:
continue
dp[lca][mask] = max(dp[lca][mask], cur + dp[lca][mask | mask1])
if __name__ == "__main__":
input = sys.stdin.read
data = input().split()
n, m = int(data[0]), int(data[1])
edges_input = data[2:]
global total_sum
for i in range(m):
a, b, c = map(int, edges_input[3 * i:3 * i + 3])
if c == 0:
paths[a].append(b)
paths[b].append(a)
total_sum += c
edges.append(Edge(a, b, c, 0))
par[1] = (1, 0)
dfs()
for j in range(1, MAXK + 1):
for i in range(1, n + 1):
jump[i][j] = jump[jump[i][j - 1]][j - 1]
for edge in edges:
if lvl[edge.a] % 2 != lvl[edge.b] % 2 and edge.c != 0:
continue
edge.lca = LCA(edge.a, edge.b)
edges.sort()
solve()
print(total_sum - dp[1][0])
