给定一个 $n$ 个点 $m$ 条边的无向连通图，边有非负边权，求 $\sum \limits _ {i = 2} ^ n \sum \limits _ {j = 1} ^ {i - 1} dis(i, j)$，其中 $dis(i, j)$ 表示点 $i$ 到点 $j$ 的最短路。

保证 $m - n \le 1000$。

输入格式

第一行两个正整数 $n, m$。

接下来 $m$ 行，每行三个非负整数 $u, v, w$ 表示 $u, v$ 间有一条长为 $w$ 的边。保证没有重边自环。$w \le 10 ^ 4$。

输出格式

一行一个非负整数，表示最短路和。

样例

样例输入 1

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

样例输出 1

32

数据范围与提示

对于所有数据，$2 \le n \le 10 ^ 5$，$m - n \le 1000$。