题目背景

在人类世界的第四十个千年，大贤者考尔完成了他与五百世界之主的约定，带上圣匣，同艾达人一起杀进网道，进入了被围困的赫拉要塞，最终借助死神的力量让基利曼重新苏醒。

罗伯特·基利曼凝望着此时腐朽不堪的人类帝国，满怀着对叛徒之敌的愤怒与仇恨，以及对帝国所遭受的一切的惊愕，而他将这一切贯注入不屈远征的集结之中。

毫无疑问，基里曼将击退黑暗诸神的走狗。

题目描述

在宇宙中，一共有 $n$ 颗星球等待着远征大军去征服，根据人类已知的信息，一共有 $m$ 条路径可以帮助军队进行移动，每条路径可被描述为，对于两个星球 $u_i, v_i(1 \le i \le m),u_i \neq v_i$，路径可以使得大军花费 $w_i$ 的时间从 $u_i$ 移动到 $v_i$，或者从 $v_i$ 移动到 $u_i$。

现在基里曼可以借助灵能力量使得任意两颗星球之间相互移动的时间变为 $0$，但是灵能力量只能被使用一次，为了使得此场战争的效率最高，基利曼希望 $\sum_{i = 1}^n \sum_{j = i + 1} ^{n} dis(i,j)$ 的值最小，$dis(i,j)$ 表示从第 $i$ 颗星球移动到第 $j$ 颗星球的最短时间。

现在，作为基利曼手下的顶级参谋，请你计算在最优方案下，$\sum_{i = 1}^n \sum_{j = i + 1} ^{n} dis(i,j)$ 的值最小是多少。

输入格式

输入第一行两个正整数 $n, m$，表示要征服的星球数量和路径数量。

接下来 $m$ 行，每行三个正整数 $u_i, v_i, w_i$，表示在星球 $u_i$ 和 $v_i$ 之间，有一条花费时间为 $w_i$ 的路径。

输出格式

输出一行，包含一个正整数，表示基利曼想要的最小值。

输入输出样例

输入 #1

4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2

输出 #1

14

数据范围

保证 $m$ 条路径可以使得 $n$ 颗星球可以相互到达，不存在重复的路径。

对于 $50\%$ 的数据：$2 \le n \le 80$。

对于 $100\%$ 的数据：$2 \le n \le 100,n-1 \le m \le \frac{1}{2}n(n-1),0 \le w_i\le 10^4$。