配点 : $400$ 点

問題文

自己ループと二重辺を含まない $N$ 頂点 $M$ 辺の重み付き無向連結グラフが与えられます。 $i (1 \leq i \leq M)$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を距離 $c_i$ で結びます。 ここで、自己ループは $a_i = b_i (1 \leq i \leq M)$ となる辺のことを表します。 また、二重辺は $(a_i,b_i)=(a_j,b_j)$ または $(a_i,b_i)=(b_j,a_j) (1 \leq i となる辺のことを表します。 連結グラフは、どの異なる $2$ 頂点間にも経路が存在するグラフのことを表します。
どの異なる $2$ 頂点間の、どの最短経路にも含まれない辺の数を求めてください。

制約

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

入力

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

$N$ $M$

$a_1$ $b_1$ $c_1$

$a_2$ $b_2$ $c_2$

$:$

$a_M$ $b_M$ $c_M$

出力

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

3 3
1 2 1
1 3 1
2 3 3

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

3 2
1 2 1
2 3 1

0

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