#1799. 最短路求和

    ID: 1799 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1424来源:qoj.ac数据:公开样例最短路径

最短路求和

最短路求和

题目描述

标题: 最短路求和 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

保证 m−n≤1000。

输入格式

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

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

输出格式

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

样例

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

数据范围与提示

子任务编号子任务限制分数1n≤300102m−n=−1103m−n=0104m−n≤20305m−n≤200106无特殊限制30

对于所有数据,2≤n≤105,m−n≤1000。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
32