题目描述

You are given an undirected connected weighted graph with $N$ vertices and $M$ edges that contains neither self-loops nor double edges.
The $i$-th $(1≤i≤M)$ edge connects vertex $a_i$ and vertex $b_i$ with a distance of $c_i$.
Here, a self-loop is an edge where $a_i = b_i (1≤i≤M)$, and double edges are two edges where $(a_i,b_i)=(a_j,b_j)$ or $(a_i,b_i)=(b_j,a_j) (1≤i \lt j≤M)$.
A connected graph is a graph where there is a path between every pair of different vertices.
Find the number of the edges that are not contained in any shortest path between any pair of different vertices.

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

输入格式

输入内容按以下格式标准输入：

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

输出格式

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

样例 #1

样例输入 #1

3 3
1 2 1
1 3 1
2 3 3

样例输出 #1

1

样例 #2

样例输入 #2

3 2
1 2 1
2 3 1

样例输出 #2

0

样例 #3

样例输入 #3

样例输出 #3

说明

数据规模与约定

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

样例 $1$ 解释

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

• 从顶点 $1$ 到顶点 $2$ 的最短路径是：顶点 $1$ →顶点{743648236}，其长度为{743648236}。→ 顶点 $2$ ，长度为 $1$ 。
• 从顶点 $1$ 到顶点 $3$ 的最短路径是：顶点 $1$ →顶点{73670751}。→ 顶点 $3$ ，长度为 $1$ 。
• 从顶点 $2$ 到顶点 $1$ 的最短路径是：顶点 $2$ →顶点{40543226}。→ 顶点 $1$ ，长度为 $1$ 。
• 从顶点 $2$ 到顶点 $3$ 的最短路径是：顶点 $2$ →顶点{x3243109}。→ 顶点 $1$ → 顶点 $3$ ，长度为 $2$ 。
• 从顶点 $3$ 到顶点 $1$ 的最短路径是：顶点 $3$ →顶点{x $1$ 。→ 顶点 $1$ ，路径长为 $1$ 。
• 从顶点 $3$ 到顶点 $2$ 的最短路径是：顶点 $3$ →顶点{x243941}。顶点 $1$ →顶点 $2$ 。→ 顶点 $2$ ，长度为 $2$ 。

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

样例 $2$ 解释

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