题目描述

题目译自 USACO 2019 February Contest, Platinum Problem 2. Moorio Kart

Bessie 和 FJ 都喜欢山羊卡丁车比赛。这个比赛与其他人喜欢的卡丁车比赛非常相似，只是卡丁车是由山羊拉的，赛道是由附近的农田组成的。农田由 $N$ 块草地和 $M$ 条道路组成，每条道路连接一对草地。

Bessie 想使用附近的农场设计一条路线。农场是两块或更多草地的子集，其中每块草地都可以沿着唯一的道路序列到达其他每块草地。

附近的农田可能包含多个农场。假设有 $K$ 个农场。Bessie 想通过增加长度为 $X$ 的 $K$ 条道路来连接所有 $K$ 个农场，形成一个山羊卡丁车环路。每个农场都应该恰好经过一次，而且每个农场内至少要有一条道路作为赛道。

为了使赛车手感到有趣，赛道的总长度至少应该是 $Y$。Bessie 想知道，在所有这样有趣的赛道上，赛道总长度的总和。如果在一条赛道上有两块相邻的草地（加上农场之间的道路后），而在另一条赛道上没有，那么这条赛道就与另一条不同。请注意，只有选择的道路是重要的，山羊卡丁车沿着这些道路行驶的方向并不重要。

输入格式

第一行包含四个整数 $N,M,X,Y\ (1\le N\le 1500,1\le M\le N-1,0\le X,Y\le 2500)$。

接下来 $M$ 行描述道路。每行三个整数 $A_i,B_i,D_i\ (1\le A_i,B_i\le N,0\le D_i\le 2500)$，表示草地 $A_i$ 和 $B_i$ 被一条长为 $D_i$ 的道路相连。每块草地至少与一条路相连，并且道路不会出现环。

输出格式

输出所有有趣的赛道的长度和。由于这个数会很大，输出它对 $10^9+7$ 取模后的值。

5 3 1 12
1 2 3
2 3 4
4 5 6

54

数据范围与提示

在至少 $70\%$ 的数据中，有 $N,Y\le 10^3$。