题解

#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;
 
namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;
 
    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
 
    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }
 
    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;
 
const int MAXN=1500+7,MAXY=2500+7,mod=1e9+7;
 
static int n,m;
 
static struct edge
{
    int v,w,nxt;
}p[MAXN<<1];
 
static int head[MAXN],e;
 
inline void add(int u,int v,int w)
{p[++e]=(edge){v,w,head[u]},head[u]=e;}
 
namespace DSU
{
    static int fa[MAXN];
 
    inline void clear(){Rep(i,1,n)fa[i]=i;}
 
    inline int Find(int u){return u==fa[u]?u:fa[u]=Find(fa[u]);}
}
 
static int X,Y;
 
inline void init()
{
    read(n),read(m),read(X),read(Y);
    DSU::clear();
    static int u,v,w;
    Rep(i,1,m)read(u),read(v),read(w)
        ,add(u,v,w),add(v,u,w),DSU::fa[DSU::Find(u)]=DSU::Find(v);
}
 
static int cn;
 
static int bel[MAXN],dst[MAXN][MAXY],sig[MAXN][MAXY];
 
void dftag(int u,int fr,int dir)
{
    bel[u]=dir;
    for(register int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].v;
        if(v^fr)dftag(v,u,dir);
    }
}
 
void dffix(int u,int fr,int len)
{
    if(fr)(sig[bel[u]][min(Y,len)]+=len)%=mod,++dst[bel[u]][min(Y,len)];
    for(register int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].v;
        if(v^fr)dffix(v,u,len+p[i].w);
    }
}
 
static int dp[MAXY][2],las[MAXY][2];
 
inline int fac(int u)
{
    register int sm=1;
    Rep(i,2,u)sm=(ll)sm*i%mod;
    return sm;
}
 
inline void solve()
{
    Rep(i,1,n)if(DSU::Find(i)==i)++cn,dftag(i,0,cn);
    Rep(i,1,n)dffix(i,0,0);
    static int st=min(Y,X*cn);
    dp[st][0]=1,dp[st][1]=X*cn;
    Rep(i,1,cn)
    {
        Rep(j,st,Y)las[j][0]=dp[j][0]
            ,las[j][1]=dp[j][1],dp[j][0]=dp[j][1]=0;
        Rep(j,0,Y)if(dst[i][j])Rep(k,st,Y)if(las[k][0])
        {
            dp[min(j+k,Y)][0]=(dp[min(j+k,Y)][0]+
                (ll)las[k][0]*dst[i][j])%mod;
 
            dp[min(j+k,Y)][1]=(dp[min(j+k,Y)][1]+
                (ll)las[k][0]*sig[i][j]+(ll)las[k][1]*dst[i][j])%mod;
        }
    }
    cout<<(ll)dp[Y][1]*fac(cn-1)%mod*((mod+1)/2)%mod<<endl;
}
 
int main()
{
    init();
    solve();
    return 0;
}