← 返回题目列表

AtCoder · code_festival_2018_final_a

A. 数字 2540

中文机器翻译题面 查看原题

配点 : 300 点

問題文

N 站,M 由真实的铁轨连接。

線路 i 是车站 A_i 和车站 B_i 直连,路由长度为 L_i 米。 满足

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