对外和平、对内和睦，是美好的事。
- 吕贝克一座旧城门上的铭文
若干城市为了保护商人的安全并促进贸易，结成了贸易同盟。你是负责管理同盟公共基金的会计。
同盟希望鼓励成员城市之间开展新的交易。因此，对于每一对不同的成员城市，同盟决定补贴它们首次交易中运输一箱货物的费用，每对城市仅补贴一次。
同盟共有 座成员城市，编号为 到 。任意两座不同的成员城市之间都有一条可以直接运输货物的双向贸易路线。从城市 向城市 直接运输一箱货物的费用如下。
第一行给出整数 和 ，以空格分隔。
输出同盟需要准备的补贴总额。
在样例 1 中，、、、、、 的最小运输费用分别为 、、、、、。因此，所需补贴总额为 。
其中， 是非负整数， 表示 除以 的余数。
货物也可以经由其他成员城市运输。一箱货物的运输费用等于运输路径上各条贸易路线的费用之和。商人会选择费用最小的路径。每笔交易的运输费用均独立计算，不受其他交易影响。
改变运输方向不会改变最小运输费用，同盟对每对城市只补贴一次。因此，所需补贴总额等于：对于所有满足 的城市对 ，将从城市 向城市 运输一箱货物的最小费用相加。请求出同盟需要准备的补贴总额。
在样例 2 中，、、 的最小运输费用分别为 、、。因此，所需补贴总额为 。
