import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
# Constants
MAXN = 5001
MAXK = 10
# Global variables
dp = [[0] * (1 << 10) for _ in range(MAXN)]
in_time = [0] * MAXN
out_time = [0] * MAXN
lol = [0] * MAXN
deg = [0] * MAXN
adj = defaultdict(list)
pr = [(0, 0)] * MAXN
timer = 0
class Road:
def __init__(self, l, r, cost, lca=0):
self.l = l
self.r = r
self.cost = cost
self.lca = lca
def __lt__(self, other):
return out_time[self.lca] < out_time[other.lca]
def dfs(node, parent):
global timer
timer += 1
in_time[node] = timer
lol[node] = lol[parent] ^ 1
for neighbor in adj[node]:
if neighbor != parent:
pr[neighbor] = (node, 1 << deg[node])
deg[node] += 1
dfs(neighbor, node)
timer += 1
out_time[node] = timer
def is_parent(A, B):
return in_time[A] <= in_time[B] and out_time[A] >= out_time[B]
def find_lca(A, B):
while not is_parent(A, B):
A = pr[A][0]
return A
def main():
input = sys.stdin.read
data = input().split()
n, m = int(data[0]), int(data[1])
roads = []
total_cost = 0
idx = 2
for _ in range(m):
a, b, c = map(int, data[idx:idx+3])
idx += 3
total_cost += c
if c == 0:
adj[a].append(b)
adj[b].append(a)
roads.append(Road(a, b, c))
dfs(1, 0)
for road in roads:
road.lca = find_lca(road.l, road.r)
roads.sort()
for road in roads:
if road.cost and (lol[road.l] ^ lol[road.r]) == 1:
continue
cost_accumulated = road.cost
A, B = (road.l, 0), (road.r, 0)
while A[0] != road.lca:
cost_accumulated += dp[A[0]][A[1]]
A = pr[A[0]]
while B[0] != road.lca:
cost_accumulated += dp[B[0]][B[1]]
B = pr[B[0]]
for mask in range((1 << deg[road.lca]) - 1, -1, -1):
if mask & (A[1] | B[1]) == 0:
dp[road.lca][mask] = max(
dp[road.lca][mask],
cost_accumulated + dp[road.lca][mask | A[1] | B[1]]
)
print(total_cost - dp[1][0])
if __name__ == "__main__":
main()
