AtCoder Regular Contest 093 - Bichrome Spanning Tree

We have an undirected weighted graph with N vertices and M edges.
The i-th edge in the graph connects Vertex U_i and Vertex V_i, and has a weight of W_i.
Additionally, you are given an integer X.
Find the number of ways to paint each edge in this graph either white or black such that the following condition is met, modulo 10^9 + 7:
 - The graph has a spanning tree that contains both an edge painted white and an edge painted black. Furthermore, among such spanning trees, the one with the smallest weight has a weight of X.
Here, the weight of a spanning tree is the sum of the weights of the edges contained in the spanning tree.

-----Constraints-----
 - 1 \leq N \leq 1 000
 - 1 \leq M \leq 2 000
 - 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
 - 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
 - If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).
 - U_i \neq V_i (1 \leq i \leq M)
 - The given graph is connected.
 - 1 \leq X \leq 10^{12}
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
X
U_1 V_1 W_1
U_2 V_2 W_2
:
U_M V_M W_M

-----Output-----
Print the answer.

-----Sample Input-----
3 3
2
1 2 1
2 3 1
3 1 1

-----Sample Output-----
6

Difficulty: VERY_HARD

Starter code:

Solutions:
from sys import stdin
import sys

def uf_find(n, p):
	ufl = []
	while p[n] != n:
		ufl.append(n)
		n = p[n]
	for i in ufl:
		p[i] = n
	return n

def uf_union(a, b, p, rank):
	ap = uf_find(a, p)
	bp = uf_find(b, p)
	if ap == bp:
		return False
	else:
		if rank[ap] > rank[bp]:
			p[bp] = ap
		elif rank[ap] < rank[bp]:
			p[ap] = bp
		else:
			p[bp] = ap
			rank[ap] += 1
		return True
(N, M) = map(int, stdin.readline().split())
X = int(stdin.readline())
wvu = []
for i in range(M):
	(u, v, w) = map(int, stdin.readline().split())
	wvu.append((w, v - 1, u - 1))
overX = 0
justX = 0
underX = 0
wvu.sort()
for i in range(M):
	p = [i for i in range(N)]
	rank = [0] * N
	h = 0
	h += wvu[i][0]
	uf_union(wvu[i][1], wvu[i][2], p, rank)
	for j in range(M):
		if uf_union(wvu[j][1], wvu[j][2], p, rank):
			h += wvu[j][0]
	if h > X:
		overX += 1
	elif h == X:
		justX += 1
	else:
		underX += 1
print(overX, justX, underX, file=sys.stderr)
ans = 0
mod = 10 ** 9 + 7
if justX == 0:
	ans = 0
elif underX > 0:
	ans = 2 * pow(2, overX, mod) * (pow(2, justX, mod) - 1)
else:
	ans = pow(2, overX, mod) * (pow(2, justX, mod) - 2)
print(ans % mod)


import sys
input = sys.stdin.readline

def find_parent(x):
	y = parent[x]
	if y < 0:
		return x
	parent[x] = find_parent(y)
	return parent[x]

def connect(a, b):
	c = find_parent(a)
	d = find_parent(b)
	if c == d:
		return
	if parent[c] < parent[d]:
		parent[c] += parent[d]
		parent[d] = c
	else:
		parent[d] += parent[c]
		parent[c] = d
	return

def f(S, G):
	que = [S]
	flag = [0] * (N + 1)
	L = [0] * (N + 1)
	flag[S] = 1
	while que:
		H = []
		for u in que:
			for (v, l) in data[u]:
				if flag[v] == 0:
					flag[v] = u
					L[v] = l
					H.append(v)
				if v == G:
					break
			else:
				continue
			break
		else:
			que = H
			continue
		break
	qqq = 0
	que = G
	while que != S:
		qqq = max(qqq, L[que])
		que = flag[que]
	return qqq
(N, M) = map(int, input().split())
X = int(input())
inf = float('inf')
mod = 10 ** 9 + 7
edge = []
for i in range(M):
	(U, V, W) = map(int, input().split())
	edge.append([W, U, V])
edge.sort()
parent = [-1] * (N + 1)
remain_edge = []
data = [[] for i in range(N + 1)]
weigh = 0
for (l, a, b) in edge:
	if find_parent(a) == find_parent(b):
		remain_edge.append([l, a, b])
		continue
	else:
		connect(a, b)
		weigh += l
		data[a].append([b, l])
		data[b].append([a, l])
if weigh > X:
	print(0)
	sys.exit()
elif weigh == X:
	count = N - 1
	for (l, a, b) in remain_edge:
		if l == f(a, b):
			count += 1
	print(pow(2, M - count, mod) * (pow(2, count, mod) - 2) % mod)
else:
	count_1 = 0
	count_2 = 0
	count_3 = 0
	for (l, a, b) in remain_edge:
		if weigh - f(a, b) + l == X:
			count_1 += 1
		elif weigh - f(a, b) + l < X:
			count_2 += 1
		else:
			count_3 += 1
	print(2 * pow(2, count_3, mod) * (pow(2, count_1, mod) - 1) % mod)


(N, M) = map(int, input().split())
X = int(input())
E = []
C = {}
for i in range(M):
	(u, v, w) = map(int, input().split())
	E.append((w, u - 1, v - 1))
	C[w] = C.get(w, 0) + 1
E.sort()
(*p,) = range(N)

def root(x):
	if x == p[x]:
		return x
	y = p[x] = root(p[x])
	return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if px == py:
		return 0
	if px < py:
		p[py] = px
	else:
		p[px] = py
	return 1
MOD = 10 ** 9 + 7
G0 = [[] for i in range(N)]
K = 0
last = None
U = [0] * M
cost = 0
for i in range(M):
	(w, u, v) = E[i]
	if unite(u, v):
		cost += w
		U[i] = 1
		if last != w:
			K += C[w]
		G0[u].append((v, w))
		G0[v].append((u, w))
		last = w

def dfs0(u, p, t, cost):
	if u == t:
		return 0
	for (v, w) in G0[u]:
		if v == p:
			continue
		r = dfs0(v, u, t, cost)
		if r is not None:
			return r | (w == cost)
	return None

def dfs1(u, p, t):
	if u == t:
		return 0
	for (v, w) in G0[u]:
		if v == p:
			continue
		r = dfs1(v, u, t)
		if r is not None:
			return max(r, w)
	return None
if X - cost < 0:
	print(0)
	exit(0)
K = 0
for i in range(M):
	if U[i]:
		K += 1
		continue
	(w, u, v) = E[i]
	if dfs0(u, -1, v, w):
		K += 1
		U[i] = 1
if cost == X:
	ans = (pow(2, K, MOD) - 2) * pow(2, M - K, MOD) % MOD
	print(ans)
	exit(0)
L = 0
G = 0
for i in range(M):
	(w, u, v) = E[i]
	if last + (X - cost) < w:
		break
	G += 1
	if U[i]:
		continue
	r = dfs1(u, -1, v) + (X - cost)
	if r == w:
		L += 1
	elif r < w:
		G -= 1
ans = 2 * (pow(2, L, MOD) - 1) * pow(2, M - G, MOD) % MOD
print(ans)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
X = int(input())
UVW = [[int(x) for x in input().split()] for _ in range(M)]
UVW.sort(key=lambda x: x[2])
root = list(range(N + 1))

def find_root(x):
	y = root[x]
	if x == y:
		return x
	z = find_root(y)
	root[x] = z
	return z
tree = [set() for _ in range(N + 1)]
min_tree_size = 0
for (u, v, w) in UVW:
	ru = find_root(u)
	rv = find_root(v)
	if ru == rv:
		continue
	root[ru] = rv
	min_tree_size += w
	tree[u].add((v, w))
	tree[v].add((u, w))
parent = [[0] * 12 for _ in range(N + 1)]
max_wt = [[0] * 12 for _ in range(N + 1)]
depth = [0] * (N + 1)

def dfs(v=1, p=0, dep=0, w=0):
	parent[v][0] = p
	depth[v] = dep
	max_wt[v][0] = w
	for n in range(1, 11):
		parent[v][n] = parent[parent[v][n - 1]][n - 1]
		max_wt[v][n] = max(max_wt[v][n - 1], max_wt[parent[v][n - 1]][n - 1])
	for (u, w) in tree[v]:
		if u == p:
			continue
		dfs(u, v, dep + 1, w)
dfs()

def max_wt_between(x, y):
	wt = 0
	(dx, dy) = (depth[x], depth[y])
	if dx > dy:
		(x, y) = (y, x)
		(dx, dy) = (dy, dx)
	while dy > dx:
		diff = dy - dx
		step = diff & -diff
		n = step.bit_length() - 1
		wt = max(wt, max_wt[y][n])
		y = parent[y][n]
		dy -= step
	if x == y:
		return wt
	step = 1 << 11
	while step:
		n = step.bit_length() - 1
		(rx, ry) = (parent[x][n], parent[y][n])
		if rx != ry:
			wt = max(wt, max_wt[x][n], max_wt[y][n])
			(x, y) = (rx, ry)
		step >>= 1
	return max(wt, max_wt[x][0], max_wt[y][0])
min_size = []
for (u, v, w) in UVW:
	if (v, w) in tree[u]:
		min_size.append(min_tree_size)
	else:
		x = max_wt_between(u, v)
		min_size.append(min_tree_size + w - x)
sm = sum((1 if s < X else 0 for s in min_size))
eq = sum((1 if s == X else 0 for s in min_size))
gr = sum((1 if s > X else 0 for s in min_size))
if eq == 0:
	answer = 0
elif sm == 0:
	answer = (pow(2, eq, MOD) - 2) * pow(2, gr, MOD) % MOD
else:
	answer = 2 * (pow(2, eq, MOD) - 1) * pow(2, gr, MOD) % MOD
print(answer)


import sys
from operator import itemgetter

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n

	def _root(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self._root(self.table[x])
			return self.table[x]

	def find(self, x, y):
		return self._root(x) == self._root(y)

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			self.table[r1] += d2
		else:
			self.table[r1] = r2
			self.table[r2] += d1

class LcaDoubling:

	def __init__(self, n, links, root=0):
		self.depths = [-1] * n
		self.max_paths = [[-1] * (n + 1)]
		self.ancestors = [[-1] * (n + 1)]
		self._init_dfs(n, links, root)
		prev_ancestors = self.ancestors[-1]
		prev_max_paths = self.max_paths[-1]
		max_depth = max(self.depths)
		d = 1
		while d < max_depth:
			next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
			next_max_paths = [max(prev_max_paths[p], prev_max_paths[q]) for (p, q) in enumerate(prev_ancestors)]
			self.ancestors.append(next_ancestors)
			self.max_paths.append(next_max_paths)
			d <<= 1
			prev_ancestors = next_ancestors
			prev_max_paths = next_max_paths

	def _init_dfs(self, n, links, root):
		q = [(root, -1, 0, 0)]
		direct_ancestors = self.ancestors[0]
		direct_max_paths = self.max_paths[0]
		while q:
			(v, p, dep, max_path) = q.pop()
			direct_ancestors[v] = p
			self.depths[v] = dep
			direct_max_paths[v] = max_path
			q.extend(((u, v, dep + 1, w) for (u, w) in links[v] if u != p))
		return direct_ancestors

	def get_lca_with_max_path(self, u, v):
		(du, dv) = (self.depths[u], self.depths[v])
		if du > dv:
			(u, v) = (v, u)
			(du, dv) = (dv, du)
		tu = u
		(tv, max_path) = self.upstream(v, dv - du)
		if u == tv:
			return (u, max_path)
		for k in range(du.bit_length() - 1, -1, -1):
			mu = self.ancestors[k][tu]
			mv = self.ancestors[k][tv]
			if mu != mv:
				max_path = max(max_path, self.max_paths[k][tu], self.max_paths[k][tv])
				tu = mu
				tv = mv
		lca = self.ancestors[0][tu]
		assert lca == self.ancestors[0][tv]
		max_path = max(max_path, self.max_paths[0][tu], self.max_paths[0][tv])
		return (lca, max_path)

	def upstream(self, v, k):
		i = 0
		mp = 0
		while k:
			if k & 1:
				mp = max(mp, self.max_paths[i][v])
				v = self.ancestors[i][v]
			k >>= 1
			i += 1
		return (v, mp)

def construct_spanning_tree(n, uvw):
	uft = UnionFind(n)
	spanning_links = [set() for _ in range(n)]
	not_spanning_links = []
	adopted_count = 0
	adopted_weight = 0
	i = 0
	while adopted_count < n - 1:
		(u, v, w) = uvw[i]
		if uft.find(u, v):
			not_spanning_links.append(uvw[i])
		else:
			spanning_links[u].add((v, w))
			spanning_links[v].add((u, w))
			uft.union(u, v)
			adopted_count += 1
			adopted_weight += w
		i += 1
	not_spanning_links.extend(uvw[i:])
	return (adopted_weight, spanning_links, not_spanning_links)

def solve(n, m, x, uvw):
	(mst_weight, spanning_links, not_spanning_links) = construct_spanning_tree(n, uvw)
	if x < mst_weight:
		return 0
	diff = x - mst_weight
	lcad = LcaDoubling(n, spanning_links)
	(lower_count, exact_count, upper_count) = (0, 0, 0)
	for (u, v, w) in not_spanning_links:
		(lca, mp) = lcad.get_lca_with_max_path(u, v)
		inc = w - mp
		if inc < diff:
			lower_count += 1
		elif inc > diff:
			upper_count += 1
		else:
			exact_count += 1
	MOD = 10 ** 9 + 7
	replace_to_exact_link = 2 * (pow(2, exact_count, MOD) - 1) * pow(2, upper_count, MOD) % MOD
	if diff > 0:
		return replace_to_exact_link
	use_first_spanning = (pow(2, n - 1, MOD) - 2) * pow(2, m - n + 1, MOD) % MOD
	return (use_first_spanning + replace_to_exact_link) % MOD
(n, m) = list(map(int, input().split()))
x = int(input())
uvw = []
for line in sys.stdin:
	(u, v, w) = list(map(int, line.split()))
	u -= 1
	v -= 1
	uvw.append((u, v, w))
uvw.sort(key=itemgetter(2))
print(solve(n, m, x, uvw))


import sys
mod = 10 ** 9 + 7
sys.setrecursionlimit(mod)
input = sys.stdin.readline

def root(v):
	if v == par[v]:
		return v
	par[v] = root(par[v])
	return par[v]

def unite(u, v):
	u = root(u)
	v = root(v)
	if u == v:
		return
	if rank[u] < rank[v]:
		(u, v) = (v, u)
	par[v] = u
	if rank[u] == rank[v]:
		rank[u] += 1

def same(u, v):
	return root(u) == root(v)

def kruskal(edges):
	tree = [[] for _ in range(N)]
	used = [False] * M
	weight = 0
	for (i, (w, u, v)) in enumerate(edges):
		if same(u, v):
			continue
		unite(u, v)
		weight += w
		tree[u].append((w, v))
		tree[v].append((w, u))
		used[i] = True
	return (weight, tree, used)

def dfs(v=0, p=-1, d=0, w=0):
	parent[0][v] = p
	depth[v] = d
	max_w[0][v] = w
	for (w, u) in T[v]:
		if u == p:
			continue
		dfs(u, v, d + 1, w)

def lca(u, v):
	if depth[u] > depth[v]:
		(u, v) = (v, u)
	tmp = 0
	while depth[v] > depth[u]:
		diff = depth[v] - depth[u]
		k = diff.bit_length() - 1
		tmp = max(tmp, max_w[k][v])
		v = parent[k][v]
	if u == v:
		return tmp
	for k in range(logN - 1, -1, -1):
		if parent[k][u] != parent[k][v]:
			tmp = max(tmp, max_w[k][u], max_w[k][v])
			u = parent[k][u]
			v = parent[k][v]
	return max(tmp, max_w[0][u], max_w[0][v])

def modpow(x, p):
	if p == 0:
		return 1
	elif p == 1:
		return x % mod
	if p % 2 == 1:
		return x * modpow(x, p - 1) % mod
	return modpow(x * x % mod, p // 2) % mod
(N, M) = map(int, input().split())
logN = (N - 1).bit_length()
X = int(input())
E = [tuple()] * M
for i in range(M):
	(u, v, w) = map(int, input().split())
	E[i] = (w, u - 1, v - 1)
E = sorted(E, key=lambda x: x[0])
par = list(range(N))
rank = [1] * N
(W, T, F) = kruskal(E)
depth = [0] * N
parent = [[0] * N for _ in range(logN + 1)]
max_w = [[0] * N for _ in range(logN + 1)]
dfs()
for k in range(logN):
	for v in range(N):
		if parent[k][v] < 0:
			parent[k + 1][v] = -1
			max_w[k + 1][v] = max_w[k][v]
		else:
			parent[k + 1][v] = parent[k][parent[k][v]]
			max_w[k + 1][v] = max(max_w[k][v], max_w[k][parent[k][v]])
le = 0
eq = 0
ge = 0
for (i, (w, u, v)) in enumerate(E):
	s = W
	if not F[i]:
		s += w - lca(u, v)
	if s < X:
		le += 1
	elif s == X:
		eq += 1
	else:
		ge += 1
ans = 0
if eq != 0:
	if le == 0:
		ans = (modpow(2, eq) - 2) * modpow(2, ge) % mod
	else:
		ans = 2 * (modpow(2, eq) - 1) * modpow(2, ge) % mod
print(ans)


import sys
from operator import itemgetter
readline = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 6)

class UF:

	def __init__(self, num):
		self.par = [-1] * num
		self.size = [1] * num

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			x = self.par[x]
			return self.find(x)

	def union(self, x, y):
		rx = self.find(x)
		ry = self.find(y)
		if rx != ry:
			if self.par[rx] < self.par[ry]:
				self.par[ry] = rx
				self.size[rx] += self.size[ry]
			elif self.par[rx] > self.par[ry]:
				self.par[rx] = ry
				self.size[ry] += self.size[rx]
			else:
				self.par[rx] -= 1
				self.par[ry] = rx
				self.size[rx] += self.size[ry]
		return

def parorder(Edge, p):
	N = len(Edge)
	Cs = [None] * N
	par = [0] * N
	par[p] = -1
	stack = [p]
	order = []
	visited = set([p])
	ast = stack.append
	apo = order.append
	while stack:
		vn = stack.pop()
		apo(vn)
		for (vf, cost) in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			Cs[vf] = cost
			ast(vf)
	return (par, order, Cs)

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p[1:], 1):
		res[v].append(i)
	return res
MOD = 10 ** 9 + 7
(N, M) = map(int, readline().split())
X = int(readline())
Edge = []
for _ in range(M):
	(a, b, c) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge.append((c, a, b))
Edge.sort(key=itemgetter(0))
T = UF(N)
cnt = 0
idx = 0
tEdge = [[] for _ in range(N)]
oEdge = []
mst = 0
while cnt < N - 1:
	while True:
		(cost, x, y) = Edge[idx]
		rx = T.find(x)
		ry = T.find(y)
		idx += 1
		if rx != ry:
			break
		oEdge.append((cost, x, y))
	cnt += 1
	tEdge[x].append((y, cost))
	tEdge[y].append((x, cost))
	mst += cost
	T.union(x, y)
for i in range(idx, M):
	oEdge.append(Edge[i])
root = 0
(P, L, Cs) = parorder(tEdge, root)
Leng = [0] * N
for i in L[1:]:
	p = P[i]
	Leng[i] = 1 + Leng[p]
Dl = [list(range(N))] + [[P[i] for i in range(N)]]
depth = N.bit_length()
for _ in range(depth - 1):
	res = [-1] * N
	for i in range(N):
		a = Dl[-1][i]
		if a != root and a != -1:
			res[i] = Dl[-1][a]
	Dl.append(res)
data = [[0] * N] + [[0 if i == root else Cs[i] for i in range(N)]]
for j in range(depth - 1):
	res = [0] * N
	for i in range(N):
		a = Dl[j + 1][i]
		if a != root and a != -1 and data[-1][a]:
			res[i] = max(data[-1][i], data[-1][a])
	data.append(res)

def query(u0, v0):
	(u, v) = (u0, v0)
	if Leng[u] > Leng[v]:
		(u, v) = (v, u)
	dif = Leng[v] - Leng[u]
	res = 0
	for i in range(dif.bit_length()):
		if 1 << i & dif:
			res = max(res, data[i + 1][v])
			v = Dl[i + 1][v]
	ll = Leng[u].bit_length()
	for i in range(ll):
		k = ll - 1 - i
		if Dl[k + 1][v] != Dl[k + 1][u]:
			res = max(res, data[k + 1][v], data[k + 1][u])
			u = Dl[k + 1][u]
			v = Dl[k + 1][v]
	if u != v:
		res = max(res, Cs[v], Cs[u])
	return res
if mst == X:
	ans = (pow(2, N - 1, MOD) - 2) * pow(2, M - (N - 1), MOD) % MOD
else:
	ans = 0
cue = 0
ran = 0
dec = 0
for (c, u, v) in oEdge:
	me = query(u, v)
	if mst + c - me < X:
		dec += 1
	elif mst + c - me == X:
		cue += 1
	else:
		ran += 1
ans = (ans + 2 * (pow(2, cue) - 1) * pow(2, ran, MOD)) % MOD
print(ans)


class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def calc_group_num(self):
		N = len(self._parent)
		ans = 0
		for i in range(N):
			if self.find_root(i) == i:
				ans += 1
		return ans
import sys
input = sys.stdin.buffer.readline
(N, M) = map(int, input().split())
X = int(input())
mod = 10 ** 9 + 7
Edge = []
EEdge = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	Edge.append((c, a - 1, b - 1))
	EEdge.append((c, a - 1, b - 1))
Edge.sort()
base = 0
edge = [[] for i in range(N)]
uf = UnionFindVerSize(N)
for (c, a, b) in Edge:
	if not uf.is_same_group(a, b):
		uf.unite(a, b)
		base += c
		edge[a].append((b, c))
		edge[b].append((a, c))
weight = [0] * N
depth = [0] * N
parent = [0] * N
rmq = [0] * N

def wdfs(v, pv):
	for (nv, cost) in edge[v]:
		if nv != pv:
			parent[nv] = v
			depth[nv] = depth[v] + 1
			weight[nv] = cost
			rmq[nv] = max(weight[nv], weight[v])
			wdfs(nv, v)
wdfs(0, -1)
LV = (N - 1).bit_length()

def construct(prv):
	kprv = [prv]
	S = prv
	for k in range(LV):
		T = [0] * N
		for i in range(N):
			if S[i] is None:
				continue
			T[i] = S[S[i]]
		kprv.append(T)
		S = T
	return kprv
kprv = construct(parent)

def constructkrmq(r):
	krmq = [r]
	S = r
	for k in range(LV):
		T = [0] * N
		for i in range(N):
			if S[i] is None:
				continue
			T[i] = max(S[i], S[kprv[k][i]])
		krmq.append(T)
		S = T
	return krmq
krmq = constructkrmq(rmq)

def lca(u, v):
	dd = depth[v] - depth[u]
	if dd < 0:
		(u, v) = (v, u)
		dd = -dd
	for k in range(LV + 1):
		if dd & 1:
			v = kprv[k][v]
		dd >>= 1
	if u == v:
		return u
	for k in range(LV - 1, -1, -1):
		pu = kprv[k][u]
		pv = kprv[k][v]
		if pu != pv:
			u = pu
			v = pv
	return kprv[0][u]

def RMQ(u, v):
	if depth[u] == depth[v]:
		return 0
	num = depth[u] - depth[v] - 1
	pos = u
	res = weight[u]
	for i in range(LV - 1, -1, -1):
		if num >> i & 1 == 1:
			res = max(res, krmq[i][pos])
			pos = kprv[i][pos]
	return res
up = 0
down = 0
same = 0
for (c, u, v) in EEdge:
	LCA = lca(u, v)
	minus = max(RMQ(u, LCA), RMQ(v, LCA))
	if base - minus + c > X:
		up += 1
	elif base - minus + c < X:
		down += 1
	else:
		same += 1
if down == 0:
	if same == 0:
		print(0)
	else:
		ans = pow(2, M, mod) - 2 * pow(2, up, mod)
		print(ans % mod)
else:
	ans = 2 * (pow(2, same, mod) - 1) * pow(2, up, mod)
	print(ans % mod)


import sys
from bisect import *
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
	md = 10 ** 9 + 7

	def get_group(k):
		g = pd[k]
		if g < 0:
			return k
		gg = get_group(g)
		pd[k] = gg
		return gg

	def merge(j, k):
		g1 = get_group(j)
		g2 = get_group(k)
		if g1 != g2:
			d1 = -pd[g1]
			d2 = -pd[g2]
			if d2 > d1:
				(g1, g2) = (g2, g1)
			pd[g2] = g1
			if d1 == d2:
				pd[g1] -= 1
	(n, m) = map(int, input().split())
	x = int(input())
	ee = []
	for _ in range(m):
		(u, v, w) = map(int, input().split())
		ee.append((w, u - 1, v - 1))
	ee.sort()
	n_nodes = n - 1
	pd = [-1] * (n_nodes + 1)
	dd = [-1] * m
	s = 0
	for i in range(m):
		(w, u, v) = ee[i]
		if get_group(u) == get_group(v):
			continue
		s += w
		merge(u, v)
		dd[i] = 0
	if s > x:
		print(0)
		exit()
	for i in range(m):
		if dd[i] == 0:
			dd[i] = s
	for si in range(m):
		if dd[si] != -1:
			continue
		pd = [-1] * (n_nodes + 1)
		(w, u, v) = ee[si]
		dd[si] = 0
		merge(u, v)
		s = w
		for i in range(m):
			(w, u, v) = ee[i]
			if get_group(u) == get_group(v):
				continue
			s += w
			merge(u, v)
			if dd[i] == -1:
				dd[i] = 0
		for i in range(m):
			if dd[i] == 0:
				dd[i] = s
	dd.sort()

	def cnt(k):
		idx = bisect_right(dd, k)
		res = pow(2, m - idx + 1, md) - 2
		if idx == 0:
			res = pow(2, m, md) - 2
		return res
	print((cnt(x - 1) - cnt(x)) % md)
main()


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n

	def root(self, x):
		while self.parent[x] != x:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def merge(self, x, y):
		(x, y) = (self.root(x), self.root(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.size[x] += self.size[y]
		self.parent[y] = x
		return True

	def issame(self, x, y):
		return self.root(x) == self.root(y)

	def getsize(self, x):
		return self.size[self.root(x)]

def largest(U, V):
	order = []
	st = [U]
	parent = [-1] * n
	wt = [0] * n
	while st:
		v = st.pop()
		if v == V:
			break
		order.append(v)
		for (c, d) in g[v]:
			if c != parent[v]:
				st.append(c)
				parent[c] = v
				wt[c] = d
	res = 0
	while V != U:
		res = max(res, wt[V])
		V = parent[V]
	return res
import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, m) = list(map(int, readline().split()))
(x,) = list(map(int, readline().split()))
uvw = [list(map(int, readline().split())) for _ in range(m)]
MOD = 10 ** 9 + 7
p2 = [1]
for _ in range(3000):
	p2.append(p2[-1] * 2 % MOD)
res = []
uvw.sort(key=lambda x: x[2])
UF = UnionFind(n)
wt = 0
g = [[] for _ in range(n)]
for i in range(m):
	(u, v, w) = uvw[i]
	if UF.merge(u - 1, v - 1):
		g[u - 1].append((v - 1, w))
		g[v - 1].append((u - 1, w))
		wt += w
	else:
		res.append(i)
ans = (p2[n - 1] - 2) * p2[m - n + 1] % MOD if wt == x else 0
free = m - n
res2 = []
for idx in res:
	(u, v, w) = uvw[idx]
	L = largest(u - 1, v - 1)
	res2.append(wt + w - L)
res2.sort()
free = m - n
for val in res2:
	if val == x:
		ans += 2 * p2[free]
	free -= 1
print(ans % MOD)