配点 : 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