AT_abc051_d.[ABC051D] Candidates of No Shortest Paths

给定一个 $N$ 个顶点 $M$ 条边的带权无向连通图，图中不包含自环和重边。
第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，距离为 $c_i$。
这里，自环指的是 $a_i = b_i$ 的边。
重边指的是存在 $i < j$，使得 $(a_i, b_i) = (a_j, b_j)$ 或 $(a_i, b_i) = (b_j, a_j)$ 的边。
连通图指的是任意两个不同的顶点之间都存在路径的图。
请你求出，在所有不同的 $2$ 个顶点之间的所有最短路径中，从未被使用过的边的数量。

输入以以下格式从标准输入读入。

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

输出在图中，从未被任何一对不同顶点之间的最短路径使用过的边的数量。

限制条件

• $2 \leq N \leq 100$
• $N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 1000\right)$
• $1 \leq a_i, b_i \leq N$
• $1 \leq c_i \leq 1000$
• $c_i$ 是整数。
• 给定的图不包含自环和重边。
• 给定的图是连通的。

样例解释 1

对于本输入样例给出的图，所有不同的 $2$ 个顶点之间的最短路径如下：

• 从顶点 $1$ 到顶点 $2$ 的最短路径为 $1 \to 2$，路径长度为 $1$
• 从顶点 $1$ 到顶点 $3$ 的最短路径为 $1 \to 3$，路径长度为 $1$
• 从顶点 $2$ 到顶点 $1$ 的最短路径为 $2 \to 1$，路径长度为 $1$
• 从顶点 $2$ 到顶点 $3$ 的最短路径为 $2 \to 1 \to 3$，路径长度为 $2$
• 从顶点 $3$ 到顶点 $1$ 的最短路径为 $3 \to 1$，路径长度为 $1$
• 从顶点 $3$ 到顶点 $2$ 的最短路径为 $3 \to 1 \to 2$，路径长度为 $2$
  因此，从未被任何最短路径使用过的边只有连接顶点 $2$ 和顶点 $3$，长度为 $3$ 的那一条，所以输出 $1$。

样例解释 2

所有的边都被某一对不同顶点之间的最短路径使用过。

由 ChatGPT 4.1 翻译