Problem:
 Score : 900 points    Problem Statement 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 1 3 3
2
1 2 1
2 3 1
3 1 1      Sample Output 1 6       Sample Input 2 3 3
3
1 2 1
2 3 1
3 1 2      Sample Output 2 2       Sample Input 3 5 4
1
1 2 3
1 3 3
2 4 6
2 5 8      Sample Output 3 0       Sample Input 4 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      Sample Output 4 4

Solution (Python):

"""

https://atcoder.jp/contests/arc093/tasks/arc093_c

各辺を含む最小全域木を考える
→重みがX未満なら、その全域木に含まれる辺は全て同一色で塗る必要がある

全ての辺に対してやれば十分？
→ではない

むしろ、X未満の全域木となった辺すべて同一色で塗る必要がある？
辺A,Bを含む全域偽は重みがX未満だが、同一色で塗る必要がないとする
→AとBの最小全域木は共有辺を一切持たない
A,Bを二つの頂点集合に分ける。頂点集合間は、別の辺l,Lで結ばれている
元の辺を除いた重みの輪を a,bとすると、 a+l < X  b+L < X である
よって、辺を交換するとどちらかは必ずX未満となる
→よって、その辺を含む最小全域木

AとBの辺を少なくとも1つづつ含む最小全域木が存在することを示せばいい
最小の重みの辺LがAにあるとする
Lに接続されている頂点Xには、Bの辺が1本ささっている
この辺を含む最小全域木をクラスカル法で構築していくと、Aの最小の辺を絶対含む
→よって、ただしい

まず、各辺を含む最小全域木を考え、重みがX未満なら白で塗る
重みがXを超える場合、重みXの全域木に含まれることはないため好きな色で塗る
→不要なため以後グラフに無いものとして扱う

今グラフには白い辺(X未満)と、未定(X)の辺がある
塗分け方は 2^X である。ここから補集合(Xの全域木を構成できない場合)を引く
全部白の場合は自明に無理

白で塗られた辺が1つ以上存在する場合を考える
黒が1つでも入っていれば構成可能？
→最小全域木に必ず白を含むことを証明できれば良い
未定の辺の最小 >= 白い辺の最小 が示せれば、白い辺の片方の頂点に来た時に絶対選ばれるのでおｋ
未定の辺が最小だった場合、片方に来た時に選ばれてしまうので示された

入っていない場合、すべて同一色でなければ構成可能？
→これも同様に証明可能なはず

"""

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)

Solution (Python):
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)

Solution (Python):
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
    else:
        if 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)

Solution (Python):
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:
    """
    links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
    というグラフ情報から、ダブリングによるLCAを構築。
    任意の2頂点のLCAおよび「パスに含まれる最長辺の長さ」を取得できるようにする
    """

    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 = map(int, input().split())
x = int(input())
uvw = []
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u -= 1
    v -= 1
    uvw.append((u, v, w))
uvw.sort(key=itemgetter(2))
print(solve(n, m, x, uvw))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)