题目描述

自己ループと二重辺を含まない $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$ 頂点間にも経路が存在するグラフのことを表します。
どの異なる $2$ 頂点間の、どの最短経路にも含まれない辺の数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

グラフ上の、どの異なる $2$ 頂点間の、どの最短経路にも含まれない辺の数を出力せよ。

题目大意

给定一个 $n$ 个点，$m$ 条边的无重边无自环的加权无向连通图，问全源最短路有几条边没被用到。

3 3
1 2 1
1 3 1
2 3 3

1

3 2
1 2 1
2 3 1

0

提示

制約

• $2≦N≦100$
• $N-1≦M≦min(N(N-1)/2,1000)$
• $1≦a_i,b_i≦N$
• $1≦c_i≦1000$
• $c_i$ は整数である。
• 与えられるグラフは自己ループと二重辺を含まない。
• 与えられるグラフは連結である。

Sample Explanation 1

この入力例で与えられるグラフにおける、全ての異なる $2$ 頂点間の最短経路は以下の通りです。 - 頂点 $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$ したがって、一度も最短経路として使用されていない辺は、頂点 $2$ と頂点 $3$ を結ぶ長さ $3$ の辺のみであるため、$1$ を出力します。

Sample Explanation 2

全ての辺が異なる $2$ 頂点間のある最短経路で使用されます。