P17356 [ECNA 2024] Balancing Art

Pete Tencious 是一位以动态雕塑闻名于世的艺术家。旧金山艺术博物馆正在展出他的一系列作品，标题分别是《平衡 I》《平衡 II》《平衡 III》……你懂这个命名规律。 每件作品包含至少两个球体，球体之间连有金属丝。每条金属丝的两端都有若干圆片，分别附着在它连接的两个球体上。把每个球体上附着的圆片数相加，所有球体得到的总数都相同，这也正是“平衡”一词的由来。Pete 把这个共同的数称为该动态雕塑的“平衡数”。有些金属丝上还悬挂着位于球体之间的额外圆片。 艺术家说，这件作品表现了自然界的平衡——附着在球体上的圆片——如何受到人类影响——球体之间的额外圆片——的破坏。显然，Pete 对自然的印象比对人类好得多。 有趣的是，大自然决定亲自给 Pete 出一道难题。湾区的一次轻微地震震松了所有圆片，现在它们全都悬挂在球体之间。Pete 正忙于创作《平衡 CCXLI》，无法联系，因此博物馆策展人只好自行修复这些动态雕塑。 策展人记不清每件作品原来的平衡数，但决定把它设得尽可能大，从而让球体之间剩余的额外圆片尽可能少。不过，求最少会剩下多少圆片并不容易，于是他们来请你帮忙。 图 1 展示了样例一对应的动态雕塑在地震后的状态。图 2 展示了策展人移动圆片的一种方式：使每个球体附着的圆片数相同，并让留在球体之间的圆片数量达到最小。 :::align{center}   :::

第一行包含两个正整数 $n,m$。其中 $2\le n\le 200$，表示动态雕塑中的球体数量，编号为 $1$ 到 $n$；$1\le m\le 500$，表示连接球体的金属丝数量。 接下来的 $m$ 行均为 $s_1,s_2,d$，其中 $1\le s_1,s_2\le n$ 且 $s_1\ne s_2$，表示一条连接球体 $s_1,s_2$ 的金属丝；$0\le d\le 10000$，表示地震后悬挂在该金属丝上的圆片数量。任意两个球体之间至多有一条金属丝。

在达到最大平衡数后，输出仍留在球体之间、悬挂于金属丝上的最少圆片数量。