Time Limit: 2 sec / Memory Limit: 256 MB

问题陈述

给你一个无向连接加权图，图中有 $N$ 个顶点和 $M$ 条边，图中既没有自循环也没有双重边。
$i$ -th $(1≤i≤M)$ 条边以 $c_i$ 的距离连接顶点 $a_i$ 和顶点 $b_i$ 。
这里的{自循环}是指 $a_i = b_i (1≤i≤M)$ 的一条边，而{双边}是指 $(a_i,b_i)=(a_j,b_j)$ 或 $( a_{i}, b_{i}) = (b_j,a_j) (1≤i < j≤M)$ 的两条边。
连接图是指每对不同顶点之间都有一条路径的图。
请找出不包含在任何一对不同顶点之间的最短路径中的边的数目。

限制因素

• $2≤N≤100$
• $N-1≤M≤min(N(N-1)/2,1000)$
• $1≤a_i,b_i≤N$
• $1≤c_i≤1000$
• $c_i$ 是整数。
• 给定图形既不包含自循环，也不包含双边。
• 给定图形是连通的。

输入

输入内容由标准输入法提供，格式如下

$N$ $M$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$ $:$
$a_M$ $b_M$ $c_M$

输出

打印图中不包含在任何一对不同顶点之间的最短路径中的边的数量。

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

样本输出 1

1

在给定的图中，所有不同顶点对之间的最短路径如下：

• 从顶点 $1$ 到顶点 $2$ 的最短路径是：顶点 $1$ → 顶点 $2$ ，长度为 $1$ 。
• 从顶点 $1$ 到顶点 $3$ 的最短路径是：顶点 $1$ →顶点{3276558}。→ 顶点 $3$ ，长度为 $1$ 。
• 从顶点 $2$ 到顶点 $1$ 的最短路径是：顶点 $2$ →顶点{860547}。→ 顶点 $1$ ，长度为 $1$ 。
• 从顶点 $2$ 到顶点 $3$ 的最短路径是：顶点 $2$ →顶点 $1$ 。→ 顶点 $1$ → 顶点 $3$ ，长度为 $2$ 。
• 从顶点 $3$ 到顶点 $1$ 的最短路径为：顶点 $3$ →顶点{2879158}。→ 顶点 $1$ ，路径长度为 $1$ 。
• 从顶点 $3$ 到顶点 $2$ 的最短路径是：顶点 $3$ →顶点{845895}。顶点 $1$ →顶点{8016265}。→ 顶点 $2$ ，长度为 $2$ 。

因此，唯一一条不包含在任何最短路径中的边是连接顶点 $2$ 和顶点 $3$ 的长度为 $3$ 的边，因此输出应该是 $1$ 。

Sample Input 2

3 2
1 2 1
2 3 1

输出示例 2

0

每一条边都包含在一对不同顶点之间的最短路径中。