#ABC243E. 全源最短路生成图的最少边数

全源最短路生成图的最少边数

题目描述

\hspace{15pt}给定一个有 nn 个顶点、mm 条边的简单带权无向连通图,顶点编号为 1∼n1\sim n,所有边权均为正整数。

\hspace{15pt}可以删除若干条边,但删除后的图必须仍然连通,且任意两个顶点之间的最短距离必须与删除前相同。

\hspace{15pt}请计算最多可以删除多少条边。输出的是删除的边数,不是最终保留的边数。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(2\leqq n\leqq300;\ n-1\leqq m\leqq n(n-1)/2\right)$。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i<v_i\leqq n;\ 1\leqq w_i\leqq10^9\right)$,代表一条无向边。

\hspace{15pt}不同边的端点对互不相同,保证图连通。

输出格式

\hspace{15pt}输出一个整数,代表在保持所有顶点对最短距离不变的条件下,最多可以删除的边数。

测试样例

3 3
1 2 2
2 3 3
1 3 6
1

样例 1 解释

\hspace{15pt}连接顶点 1,31,3 的直接边长度为 66,而经顶点 22 的路线长度为 2+3=52+3=5。删除这条直接边后,各对顶点间的距离仍为 2,3,52,3,5。其余两条边均不能再删除,因此答案为 11。

5 4
1 3 3
2 3 9
3 5 3
4 5 3
0
5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10
5