复习

好久没搞过最小生成树了，先复习一下一些比较重要的东西

kruskal的证明

考虑反证法，如果有一个生成树边集${S_1}$比kruskal跑出来的边集${S_2}$跑出来的最小生成树边集更小，我们就把所有${S_1}$的边按照权值排序，然后从小到大扫过去，扫到一条边就将其像kruskal那样添加进并查集。找到第一条添加进去的不符合kruskal算法的边$e_1$（即存在另外一条权值小于他，而且添加进去不会成环的边$e_2$）。我们发现$e_2$联通的是两个连通块，而如果${S_1}$没有选择$e_2$的话，将来一定会选择一条权值大于$e_2$的边$e_3$来联通这两个联通块，而$e_3$替换成$e_2$一定更优秀。

破圈算法

我也不知道是不是叫这个名字。意思就是说，我们可以以任意顺序加入边，如果成了环，就删掉环上最大权值的边，这样得到的一定是最小生成树。这玩意也是可以基于kruskal的证明进行证明的。我们可以归纳证明破圈算法的正确性：
对于已经添加了部分边的图$G$，其最小生成树为$T$。我们再添加一条新的边$e_1$，如果成了环，令环上的边集为$E$，$E$中最大边为$e_{max}$。我们考虑对$G\cup {e_1}$跑kruskal，当枚举到$e_1$时必定将其加入最小生成树（因为没有$e_1$时将$e_{max}$加入了最小生成树，$e_1$一定在$e_{max}$之前被枚举到）。当枚举到$e_{max}$的时候必定不会选（选了就成环了）。其他$E$中的边可以都保持不变。这样我们就得到了添加$e_1$后的图$G$的最小生成树。

这道题

分类讨论一波，令这个图最小生成树权值为$Y$

• $X<Y$
  必定无解，方案数为0.
• $X=Y$
  我们考虑随便跑个最小生成树$T$，对于$T$中边颜色不同的情况，其他边不管咋选，因为$T$的存在，还是必定满足题目要求，这样的情况数是$(2^{n-1}-2)\times 2^{m-(n-1)}$的。
  对于$T$中颜色相同的情况。我们把其他边分成$A/B$两类。$A$中的边代表使用破圈算法在$T$上加入这条边后，MST大小为X，$B$中的边则加入后大于X。
  因为$B$类边必定不会存在于任意一个最小生成树上，所以不影响答案，可以随便涂。而$A$类边只有全部和$T$为同一颜色的情况必定无解，其他情况均有解（随便选一条$T$颜色不同的$A$类边添加上去，根据破圈算法得到的$T$一定还是最小生成树）。所以这种情况数是$2\times (2^{cnt(A)}-1)\times 2^{cnt(B)}$。把两个式子加起来就是答案。
• $X>Y$
  首先$T$颜色肯定要全部相同，跑出$T$之后剩下的边中，加入之后MST小于$X$的边颜色也要和$T$相同。除此之外的边还是考虑分成$A/B$类，定义保持不变。现在手上就只需要考虑$A/B$类边了，做法就和$X=Y$情况完全相同了。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int mod=1e9+7;
const int maxn=2005;
struct GG{
	int u,v,w;
}ori[maxn];
int fa[maxn];
bool cmp(GG a,GG b){return a.w<b.w;}
int get(int x){return (fa[x]==x)?x:(fa[x]=get(fa[x]));}
void uni(int x,int y){fa[get(x)]=get(y);}
int dep[maxn],f[maxn],valtof[maxn];
vi side[maxn],W[maxn];
void dfs1(int u,int fa){
	//cout<<">>"<<u<<' '<<fa<<endl;cnt++;
//	if(cnt>10)return;
	dep[u]=dep[fa]+1;
	rep(i,0,side[u].size()-1){
		int v=side[u][i];if(v==fa)continue;
		dfs1(v,u);f[v]=u;valtof[v]=W[u][i];
	}
}
vi A,B;
int find(int u,int v){
	int mx=0;
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v);
		mx=max(mx,valtof[u]);u=f[u];
	}
	return mx;
}
int ksm(int num,int t){
	int res=1;
	for(;t;t>>=1,num=1ll*num*num%mod){
		if(t&1)res=1ll*num*res%mod;
	}
	return res;
}
int main(){
	rep(i,1,maxn-1)fa[i]=i;
	int n,m;scanf("%d%d",&n,&m);
	ll X,Y=0;scanf("%lld",&X);
	rep(i,1,m){
		scanf("%d%d%d",&ori[i].u,&ori[i].v,&ori[i].w);
		
	}
	sort(ori+1,ori+1+m,cmp);
	rep(i,1,m){
		int u=ori[i].u,v=ori[i].v;
		if(get(u)!=get(v)){
			uni(u,v);Y+=ori[i].w;
			side[ori[i].u].pb(ori[i].v);side[ori[i].v].pb(ori[i].u);
			W[ori[i].u].pb(ori[i].w);W[ori[i].v].pb(ori[i].w);
		}
	}
	dfs1(1,0);
	rep(i,1,maxn-1)fa[i]=i;
	rep(i,1,m){
		int u=ori[i].u,v=ori[i].v;
		if(get(u)!=get(v)){uni(u,v);}
		else{
			int delta=ori[i].w-find(u,v);
			if(Y+delta==X)A.pb(i);
			else if(Y+delta>X)B.pb(i);
		}
	}
	ll ans=0;
	if(X<Y){ans=0;}
	else if(X==Y){
		ans=1ll*(ksm(2,n-1)-2)*ksm(2,m-(n-1))%mod;
		//cout<<ans<<endl;
		ans=(ans+2ll*(ksm(2,A.size())-1)*ksm(2,B.size()))%mod;
	}
	else 
	ans=(ans+2ll*(ksm(2,A.size())-1)*ksm(2,B.size()))%mod;
	ans=(ans%mod+mod)%mod;
	printf("%lld",ans);
	return 0;
}