Pete Tencious 是一位专门制作动态艺术装置（mobiles）的世界知名艺术家。旧金山现代艺术博物馆目前正在展出他的一系列作品，名为 Balance I, Balance II, Balance III 等等。每一件作品都包含两个或更多的球体，球体之间由金属丝连接。在每根金属丝的两端，连接着附着在两个球体上的若干圆盘。当你将每个球体上的圆盘数量相加时，你会得到相同的总数（因此得名“平衡”——Pete 将其称为每个装置的“平衡数”）。在某些金属丝上，球体之间还悬挂着额外的圆盘。艺术家说，这件作品代表了自然的平衡（附着在球体上的圆盘）被人类的影响（球体之间额外的圆盘）所破坏。显然，Pete 对自然的印象比对人类的印象要好得多。

有趣的是，大自然决定介入并给 Pete 出个难题。湾区发生了一次小地震，导致圆盘脱落，现在它们都松散地悬挂在球体之间。Pete 目前正在制作 Balance CCXLI，无法联系上，所以博物馆馆长们必须自己修复这些装置。他们记不清每个装置的平衡数到底应该是多少，但他们决定让它尽可能大，同时让球体之间剩余的额外圆盘尽可能少（他们对人类的看法显然比某人要好一点）。然而，确定球体之间剩余的最小圆盘数量有点困难，所以他们来向你寻求帮助。

图 C.1 展示了地震后一个装置的状态，对应于第一个样例输入。图 C.2 展示了馆长们移动圆盘的一种方式，使得每个球体上的圆盘数量相同，同时使球体之间剩余的圆盘数量最少。

图 C.1：地震后

图 C.2：移动圆盘以最大化平衡数

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$，其中 $n$ ($2 \le n \le 200$) 是装置中球体的数量（编号为 $1$ 到 $n$），$m$ ($1 \le m \le 500$) 是连接球体的金属丝数量。接下来是 $m$ 行，每行格式为 $s_1 \ s_2 \ d$，其中 $s_1$ 和 $s_2$ ($1 \le s_1, s_2 \le n, s_1 \neq s_2$) 是由一根金属丝连接的两个球体，$d$ ($0 \le d \le 10\,000$) 是地震后悬挂在该金属丝上的圆盘数量。任意两个球体之间最多只有一根金属丝。

输出格式

输出在达到最大平衡数后，悬挂在球体之间金属丝上的圆盘的最小总数。

样例

样例输入 1

3 3
1 2 3
1 3 4
2 3 6

样例输出 1

1

样例输入 2

5 4
1 2 2
1 5 2
2 3 2
2 4 20

样例输出 2

16