[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}$ 后的结果。

输入输出样例

输入样例 #1

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

输出样例 #1

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 $ 。