QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+7]

# 7790. 最短路求和

Statistics

给定一个 n 个点 m 条边的无向连通图,边有非负边权,求 ni=2i1j=1dis(i,j),其中 dis(i,j) 表示点 i 到点 j 的最短路。

保证 mn1000

输入格式

第一行两个正整数 n,m

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

输出格式

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

样例

样例输入 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

数据范围与提示

子任务编号子任务限制分数
1n30010
2mn=110
3mn=010
4mn2030
5mn20010
6无特殊限制30

对于所有数据,2n105mn1000