Language: C++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 1000 + 10;
const int MAXM = 2000 + 10;

inline LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}
LL pow2[MAXM]= {0};

struct LFS { int to, w, next; };
LFS Link[MAXM << 1];
int Head[MAXN]= {0}, size = 0;
void Insert (int u, int v, int w) {
	Link[++ size].to = v;
	Link[size].w = w;
	Link[size].next = Head[u];

	Head[u] = size;
}

LL fact[MAXN]= {0}, invfact[MAXN]= {0};
LL inv[MAXN]= {0};
inline LL C (int n, int m) { return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD; }

int N, M;
LL X;
struct Edge {
	int u, v, w;
	Edge (int u = 0, int v = 0, int w = 0) : u (u), v (v), w (w) {}
	bool operator < (const Edge& p) const { return w < p.w; }
} ;
Edge edge[MAXM];

int dfn[MAXN]= {0}, ord;
int depth[MAXN], value[MAXN << 1], bel[MAXN << 1];
void DFS (int root, int father) {
	dfn[root] = ++ ord;
	value[ord] = depth[root], bel[ord] = root;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == father) continue;
		depth[v] = depth[root] + 1;
		DFS (v, root);
		value[++ ord] = depth[root];
		bel[ord] = root;
	}
}
pair<int, int> ST[MAXN << 1][15];
void RMQ () {
	for (int i = 1; i <= ord; i ++) ST[i][0] = make_pair (value[i], bel[i]);
	int MAX = log2 (ord) + 1;
	for (int j = 1; j <= MAX; j ++)
		for (int i = 1; i + (1 << j) - 1 <= ord; i ++)
			if (ST[i][j - 1].first < ST[i + (1 << (j - 1))][j - 1].first) ST[i][j] = ST[i][j - 1];
			else ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
}
inline int LCA (int x, int y) {
	if (dfn[x] > dfn[y]) swap (x, y);
	int l = dfn[x], r = dfn[y];
	int k = log2 (r - l + 1);
	if (ST[l][k].first < ST[r - (1 << k) + 1][k].first) return ST[l][k].second;
	return ST[r - (1 << k) + 1][k].second;
}
int father[MAXN][15]= {0}, maxi[MAXN][15]= {0};
void build (int root, int fa) {
	father[root][0] = fa;
	for (int j = 1; j <= 10; j ++) {
		if (! father[root][j - 1]) break;
		father[root][j] = father[father[root][j - 1]][j - 1];
		maxi[root][j] = max (maxi[root][j - 1], maxi[father[root][j - 1]][j - 1]);
	}
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to, w = Link[i].w;
		if (v == fa) continue;
		maxi[v][0] = w;
		build (v, root);
	}
}
inline LL climb (int x, int lca) {
	int ret = 0;
	for (int j = 10; j >= 0; j --) {
		if (depth[father[x][j]] < depth[lca]) continue;
		ret = max (ret, maxi[x][j]);
		x = father[x][j];
	}
	return ret;
}
bool check (int x, int y, int w) {
	int lca = LCA (x, y);
	int mret = max (climb (x, lca), climb (y, lca));
	return mret == w;
}
int fa[MAXN]= {0};
int find (int x) { return fa[x] == x ? x : fa[x] = find (fa[x]); }
LL Kruskal () {
	LL ret = 0;
	for (int i = 1; i <= M; i ++) {
		int x = edge[i].u, y = edge[i].v, w = edge[i].w;
		int fx = find (x), fy = find (y);
		if (fx == fy) continue;
		fa[fx] = fy; ret += w;
		Insert (x, y, w), Insert (y, x, w);
	}
	return ret;
}
int white[MAXN]= {0}, black[MAXN]= {0};
int wn = 0, bn = 0;
LL cencus () {
	LL ret = 0;
	for (int q = 1; q <= bn; q ++) {
		int i = black[q];
		for (int j = 1; j <= N; j ++) { fa[j] = j; Head[j] = 0; }
		size = 0;
		int u = edge[i].u, v = edge[i].v, w = edge[i].w;
		fa[u] = v;
		Insert (u, v, w), Insert (v, u, w);
		Kruskal ();
		ord = 0, depth[1] = 1, DFS (1, 0); RMQ ();
		build (1, 0);
		int m = 0;
		for (int j = 1; j <= bn; j ++)
			if (check (edge[black[j]].u, edge[black[j]].v, edge[black[j]].w))
				m ++;
		// cout << "now m: " << m << endl;
		LL add = 0;
		for (int j = 0; j <= m - 1 - (! wn); j ++)
			add = (add + C (m - 1, j) * inv[j + 1] % MOD) % MOD;
		ret = (ret + add) % MOD;
	}
	if (wn) ret = 2ll * ret % MOD;
	return ret;
}
LL solve () {
	LL ans = 0; int ext = 0;
	for (int i = 1; i <= M; i ++) {
		if (1ll * edge[i].w > X) { ext ++; continue; }
		for (int j = 1; j <= N; j ++) { fa[j] = j; Head[j] = 0; }
		size = 0;
		int u = edge[i].u, v = edge[i].v, w = edge[i].w;
		fa[u] = v;
		LL x = w + Kruskal ();
		if (x < X) white[++ wn] = i;
		else if (x == X) black[++ bn] = i;
		else ext ++;
	}
	// cout << "first: " << wn << ' ' << bn << ' ' << ext << endl;
	ans = cencus ();
	ans = ans * pow2[ext] % MOD;
	return ans;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum (); cin >> X;
	if (N == 1) { puts ("0"); return 0; }
	pow2[0] = 1;
	for (int i = 1; i <= M; i ++) pow2[i] = pow2[i - 1] * 2ll % MOD;
	fact[0] = invfact[0] = 1;
	inv[1] = fact[1] = invfact[1] = 1;
	for (int i = 2; i <= M; i ++) {
		inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
		fact[i] = fact[i - 1] * i % MOD;
		invfact[i] = invfact[i - 1] * inv[i] % MOD;
	}
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum (), w = getnum ();
		edge[i] = Edge (u, v, w);
	}
	sort (edge + 1, edge + M + 1);
	cout << solve () << endl;
	
	return 0;
}

/*
3 3
2
1 2 1
2 3 1
3 1 1
*/

/*
3 3
3
1 2 1
2 3 1
3 1 2
*/

/*
5 4
1
1 2 3
1 3 3
2 4 6
2 5 8
*/

/*
8 10
49
4 6 10
8 4 11
5 8 9
1 8 10
3 8 128773450
7 8 10
4 2 4
3 4 1
3 1 13
5 2 2
*/

Compiler output:
a.cc: In function 'void Insert(int, int, int)':
a.cc:31:17: error: reference to 'size' is ambiguous
   31 |         Link[++ size].to = v;
      |                 ^~~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:29:22: note:                 'int size'
   29 | int Head[MAXN]= {0}, size = 0;
      |                      ^~~~
a.cc:32:14: error: reference to 'size' is ambiguous
   32 |         Link[size].w = w;
      |              ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:29:22: note:                 'int size'
   29 | int Head[MAXN]= {0}, size = 0;
      |                      ^~~~
a.cc:33:14: error: reference to 'size' is ambiguous
   33 |         Link[size].next = Head[u];
      |              ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:29:22: note:                 'int size'
   29 | int Head[MAXN]= {0}, size = 0;
      |                      ^~~~
a.cc:35:19: error: reference to 'size' is ambiguous
   35 |         Head[u] = size;
      |                   ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:29:22: note:                 'int size'
   29 | int Head[MAXN]= {0}, size = 0;
      |                      ^~~~
a.cc: In function 'LL cencus()':
a.cc:130:17: error: reference to 'size' is ambiguous
  130 |                 size = 0;
      |                 ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:29:22: note:                 'int size'
   29 | int Head[MAXN]= {0}, size = 0;
      |                      ^~~~
a.cc: In function 'LL solve()':
a.cc:155:17: error: reference to 'size' is ambiguous
  155 |                 size = 0;
      |                 ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:29:22: note:                 'int size'
   29 | int Head[MAXN]= {0}, size = 0;
      |                      ^~~~