A - 2540

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

N 個の駅があり、M 本の線路で結ばれています。

線路 i は駅 A_i と駅 B_i を直接結んでおり、路線長は L_i mです。

a < c,a \neq b,b \neq c を満たす (a,b,c) の組で、駅 a と駅 b の間、駅 b と駅 c の間を直接結ぶ線路が存在し、かつ 2 つの路線長の和が 2540 mとなるものがいくつあるか求めてください。

同じ駅どうしを結ぶ路線や、線路の通らない駅が存在しないことは保証されますが、全ての駅が連結とは限りません。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • (A_i,B_i) \neq (A_j,B_j) (i \neq j)
  • 1000 \leq L_i \leq 2000
  • 入力は全て整数
  • 線路の通らない駅は存在しない

入力

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

N M
A_1 B_1 L_1
:
A_M B_M L_M

出力

条件を満たす (a,b,c) の組が x 通りあるとき、x を出力せよ。


入力例 1

4 3
1 2 1420
2 3 1120
3 4 1420

出力例 1

2

(1,2,3),(2,3,4) が条件を満たします。


入力例 2

4 2
1 2 1920
3 4 1125

出力例 2

0