AT_abc051_d [ABC051D] Candidates of No Shortest Paths

[problemUrl]: https://atcoder.jp/contests/abc051/tasks/abc051_d 自己ループと二重辺を含まない $ 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\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ : $ $ a_M $ $ b_M $ $ c_M $

グラフ上の、どの異なる $ 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 $ は整数である。 - 与えられるグラフは自己ループと二重辺を含まない。 - 与えられるグラフは連結である。 ### 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 $ 頂点間のある最短経路で使用されます。