問題文
兔子和乌龟将在ARC山上进行一场比赛。
ARC在山上 有 N 个中继点,中继点有 编号至 1 它们的编号最大为 N 。也不同 2 连接两个中继点的道路 M 有一本书。其中 2 甚至两条不同的路径也是相连的。 2 两个中继点永远不匹配。每条路径都有固定的长度。另外,Mt. ARC 上有哪些地点? 2 可以通过多条道路在两个不同的中继点之间来回。
在比赛中,目的地是从接力点中选择的。 A,兔子的起点 B, 海龟的起点 选择 C 。A,B,C 是中继点之一。 1 必须是A,B,C 必须彼此不同。比赛开始后,兔子会 R 米每秒 T 前往目的地(以米为单位)。
乌龟以最佳方式移动,这样无论兔子使用哪条路线,它都会跟随乌龟到达目的地。 A,B,C 设置 ( 我想知道总共有多少个A,B,C) 。
入力
输入是按以下格式从标准输入给出的。
N M R T a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
- 1 行显示中继点数。 N (3 ≦ N ≦ 2,500),道路数量 M (2 ≦ M ≦ 3,000),兔子速度 R (1 ≦ R ≦ 200) 和海龟速度 在 T (1 ≦ T ≦ 200) 用空格分隔。
- 2 从行 M 行中,给出了有关路径的信息。其中 i 排队 i 是 它可能以 2 两个中继点 a_i,b_i (1 ≦ a_i < b_i ≦ N) 长度是 c_i (1 ≦ c_i ≦ 100) 代表米。
出力
组合总数 在 1 行输出。在输出末尾插入换行符。
入力例1
4 5 2 1 1 2 4 1 3 3 1 4 6 2 3 5 3 4 4
出力例1
2
下面 2 街道是可能的。
- (目的地,兔子的起点,乌龟的起点)(2, 4, 1),海龟直接前往目的地。 4 秒后到达。另一方面,无论兔子走哪条路,至少 需要 4.5 秒。
- (目的地,兔子的起点,乌龟的起点)(4, 3, 2),海龟直接前往目的地。 4 秒后到达。另一方面,无论兔子走哪条路,至少 需要 4.5 秒。
超过 2 就是这样。顺便说一句,(目的地,兔子的起点,乌龟的起点)是(1, 4, 3),为了让兔子和乌龟都到达目的地, 需要超过 3 秒。如果它们以最佳方式彼此移动,它们将同时到达,因此不满足条件。
入力例2
5 4 7 7 1 2 1 2 3 1 3 4 1 4 5 1
出力例2
26