该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

徐老师的单向路网

题目描述

一座城市有 $N$ 个路口和 $M$ 条单向道路。第 $i$ 条道路从路口 $a_i$ 通向路口 $b_i$，长度为 $c_i$。

徐老师将一条道路称为有用道路，当且仅当存在一对路口 $(s,t)$，使得某条从 $s$ 到 $t$ 的最短路经过这条道路。只考虑存在从 $s$ 到 $t$ 路径的有序点对。

请计算有多少条道路不是有用道路。

输入格式

第一行输入两个整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行输入三个整数 $a_i,b_i,c_i$，表示一条从 $a_i$ 到 $b_i$、长度为 $c_i$ 的单向道路。

• $2 \le N \le 100$
• $N-1 \le M \le \min(N(N-1)/2,1000)$
• $1 \le a_i,b_i \le N$，且 $a_i\ne b_i$
• $1 \le c_i \le 1000$
• 不存在起点和终点都相同的两条道路，但可以同时存在 $u\to v$ 和 $v\to u$
• 忽略道路方向后，整张图连通

输出格式

输出一个整数，表示不属于任何最短路的道路数量。

输入输出样例 #1

输入 #1

3 3
1 2 1
2 3 1
3 1 10

输出 #1

0

输入输出样例 #2

输入 #2

3 4
1 2 5
1 3 2
3 2 1
2 1 4

输出 #2

1

说明/提示

样例 1 中，从 $3$ 到 $1$ 只能沿第三条道路前进，因此长度为 $10$ 的道路也是一条最短路的一部分，三条道路都有用。

样例 2 中，从 $1$ 到 $2$ 可以走 $1\to3\to2$，总长度为 $3$，严格短于第一条道路的长度 $5$。第一条道路无用，其余道路都有用。