[USACO19FEB] Moorio Kart P

Bessie 和 Farmer John 喜欢山羊卡丁车比赛。这个比赛非常类似于其他人喜欢的卡丁车比赛，除了卡丁车是由山羊拉动，以及赛道是由农田组成。农田由 $ N $ 个草地和 $ M $ 条道路组成，每条道路都连接着两个草地。 定义农场是两个或更多草地的一个集合，同一农场中的每个草地都可以沿着一系列**唯一**的道路到达农场中其他任意一个草地。 整个农田可能由多个农场组成，假设图中有 $ K $ 个农场。Bessie 希望通过添加长度为 $ X $ 的 $ K $ 条道路，连接所有 $ K $ 个农场来制作山羊卡丁车赛道。每个农场只应访问一次，并且每个农场内必须至少穿过一条道路。 为了让选手们对赛道更有兴趣，赛道的长度至少应该为 $ Y $ 。Bessie 希望知道所有这些有趣赛道的赛道长度总和。如果一个赛道中有两个农场直接相连，但另外一个赛道中这两个农场没有直接相连的话，这两个赛道就是不同的。 --- 形式化题意： 给定 $K$ 个连通块的森林，边有边权。你需要加入 $K$ 条长为 $X$ 的边使得整张图变成一棵基环树。原来的每个连通块在环上至少有一条边，所有新加入的边都应该在环上。 求所有环长 $\ge 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 $ 。