题目描述

您将获得一个无向连通加权图，具有 $N$ 个顶点和 $M$ 条边，其中既不包含自环也不包含重复边。
第 $i$ 条边 $(1≤i≤M)$ 连接顶点 $a_i$ 和顶点 $b_i$，距离为 $c_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$

输出

输出图中未出现在任何两个不同顶点之间的最短路径中的边的数量。

示例输入 1

3 3
1 2 1
1 3 1
2 3 3

示例输出 1

1

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

• 从顶点 $1$ 到顶点 $2$ 的最短路径为：顶点 $1$ → 顶点 $2$，长度为 $1$。
• 从顶点 $1$ 到顶点 $3$ 的最短路径为：顶点 $1$ → 顶点 $3$，长度为 $1$。
• 从顶点 $2$ 到顶点 $1$ 的最短路径为：顶点 $2$ → 顶点 $1$，长度为 $1$。
• 从顶点 $2$ 到顶点 $3$ 的最短路径为：顶点 $2$ → 顶点 $1$ → 顶点 $3$，长度为 $2$。
• 从顶点 $3$ 到顶点 $1$ 的最短路径为：顶点 $3$ → 顶点 $1$，长度为 $1$。
• 从顶点 $3$ 到顶点 $2$ 的最短路径为：顶点 $3$ → 顶点 $1$ → 顶点 $2$，长度为 $2$。

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

示例输入 2

3 2
1 2 1
2 3 1

示例输出 2

0

每条边都出现在某对不同顶点之间的某个最短路径中。