题目描述

Bessie 和 Farmer John 喜欢山羊卡丁车比赛。这个比赛非常类似于其他人喜欢的卡丁车比赛，除了卡丁车是由山羊拉动，以及赛道是由农田组成。农田由 $N$ 个草地和 $M$ 条道路组成，每条道路都连接着两个草地。

定义农场是两个或更多草地的一个集合，同一农场中的每个草地都可以沿着一系列唯一的道路到达农场中其他任意一个草地。

整个农田可能由多个农场组成，假设图中有 $K$ 个农场。Bessie 希望通过添加长度为 $X$ 的 $K$ 条道路，连接所有 $K$ 个农场来制作山羊卡丁车赛道。每个农场只应访问一次，并且每个农场内必须至少穿过一条道路。

为了让选手们对赛道更有兴趣，赛道的长度至少应该为 $Y$ 。Bessie 希望知道所有这些有趣赛道的赛道长度总和。如果一个赛道中有两个农场直接相连，但另外一个赛道中这两个农场没有直接相连的话，这两个赛道就是不同的。

形式化题意：

$K$ 个连通块的森林，边有边权。对于所有加入 $K$ 条长 $X$ 的边使图变成一个基环树，且环经过所有加入的边，且环的长度 $\geq Y$ 的方案，求环的长度的和。

输入格式

第一行包括四个整数 $N,M,X,Y$（$1 \leq N \leq 1500,1 \leq M \leq N-1,0 \leq X, Y \leq 2500$）。

接下来 $M$ 行，每行包含三个整数： $A_i,B_i,D_i$（$1 \leq A_i, B_i \leq N,0 \leq D_i \leq 2500$），代表 $A_i$ 号草地和 $B_i$ 号草地间有一条长度为 $D_i$ 的道路。保证两个草地间最多只有一条道路直接相连，且不存在自环。

输出格式

输出有趣赛道的赛道长度总和 $\pmod {10^9+7}$ 后的结果。

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

54

提示

有 6 个合法的赛道方案：

• 1 --> 2 --> 4 --> 5 --> 1 (长度 11)
• 1 --> 2 --> 5 --> 4 --> 1 (长度 11)
• 2 --> 3 --> 4 --> 5 --> 2 (长度 12)
• 2 --> 3 --> 5 --> 4 --> 2 (长度 12)
• 1 --> 2 --> 3 --> 4 --> 5 --> 1 (长度 15)
• 1 --> 2 --> 3 --> 5 --> 4 --> 1 (长度 15)

其中后 4 条赛道满足了赛道总长不低于 12 的条件，这几条赛道的长度总和为 54。

子任务：对于 $70\%$ 的数据， $N,Y \leq 1000$ 。