問題文

自己ループと二重辺を含まない $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$ 頂点間の、どの最短経路にも含まれない辺の数を求めてください。

制約

• $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$

出力

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

入力例 1

3 3
1 2 1
1 3 1
2 3 3

出力例 1

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$ を出力します。

入力例 2

3 2
1 2 1
2 3 1

出力例 2

0

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