给定一个 $ 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
数据范围与提示
| 子任务编号 | 子任务限制 | 分数 |
|---|---|---|
| $ 1 $ | $ n \le 300 $ | $ 10 $ |
| $ 2 $ | $ m - n = -1 $ | $ 10 $ |
| $ 3 $ | $ m - n = 0 $ | $ 10 $ |
| $ 4 $ | $ m - n \le 20 $ | $ 30 $ |
| $ 5 $ | $ m - n \le 200 $ | $ 10 $ |
| $ 6 $ | 无特殊限制 | $ 30 $ |
对于所有数据，$ 2 \le n \le 10 ^ 5 $，$ m - n \le 1000 $。