给定一个 n 个点 m 条边的无向连通图,边有非负边权,求 n∑i=2i−1∑j=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
数据范围与提示
子任务编号 | 子任务限制 | 分数 |
---|---|---|
1 | n≤300 | 10 |
2 | m−n=−1 | 10 |
3 | m−n=0 | 10 |
4 | m−n≤20 | 30 |
5 | m−n≤200 | 10 |
6 | 无特殊限制 | 30 |
对于所有数据,2≤n≤105,m−n≤1000。