QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 7790. 最短路求和

统计

给定一个 $ 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 $。