Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
import sys

sys.setrecursionlimit(200000)
MOD, INF = 1000000007, float('inf')


def get_patterns_func(s, ancestors):
    cache = {s: 1}

    def get_patterns(v):
        if v in cache:
            return cache[v]
        return sum(get_patterns(a) for a in ancestors[v])

    return get_patterns


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    ancestors_fwd, ancestors_bwd = defaultdict(set), defaultdict(set)
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            ancestors_self = ancestors_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            ancestors_self = ancestors_fwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        ancestors_self[v].add(a)

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            if cost == collision_time:
                ancestors_bwd[v].add(a)
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
            ancestors_fwd[v].add(a)
        else:
            collision_links.add((a, v))

    patterns_fwd = get_patterns_func(s, ancestors_fwd)
    patterns_bwd = get_patterns_func(t, ancestors_bwd)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = patterns_fwd(v) * patterns_bwd(v)
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = patterns_fwd(u) * patterns_bwd(v)
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def get_patterns_func(s, ancestors):
    cache = {s: 1}

    def get_patterns(v):
        if v in cache:
            return cache[v]
        return sum(get_patterns(a) for a in ancestors[v])

    return get_patterns


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    ancestors_fwd, ancestors_bwd = defaultdict(set), defaultdict(set)
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            ancestors_self = ancestors_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            ancestors_self = ancestors_fwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        ancestors_self[v].add(a)

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            if cost == collision_time:
                ancestors_bwd[v].add(a)
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
            ancestors_fwd[v].add(a)
        else:
            collision_links.add((a, v))

    patterns_fwd = get_patterns_func(s, ancestors_fwd)
    patterns_bwd = get_patterns_func(t, ancestors_bwd)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = patterns_fwd(v) * patterns_bwd(v)
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = patterns_fwd(u) * patterns_bwd(v)
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    dists = [(d, v) for v, d in enumerate(visited) if d != INF]
    dists.sort()
    for dv, v in dists:
        for du, u in links[v]:
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return dists, counts


def solve(s, t, links):
    q = [(0, s, 0), (0, t, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    limit = 0
    while q:
        cost, v, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        pre_cost = visited_self[v]
        if pre_cost == INF:
            visited_self[v] = cost
        elif cost > pre_cost:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            break

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, is_bwd))

    collision_time = limit / 2
    while q:
        cost, v, is_bwd = heappop(q)
        if cost > collision_time:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if cost < visited_self[v]:
            visited_self[v] = cost

    dists_fwd, counts_fwd = count_routes(visited_fwd, s, links)
    dists_bwd, counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for d_fwd, v in dists_fwd[:bisect(dists_fwd, (collision_time, n))]:
        d_bwd = visited_bwd[v]
        if d_fwd == d_bwd:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += pow(r, 2, MOD)
            collision_count %= MOD
        else:
            ct = collision_time - d_fwd
            lt = limit - d_fwd
            for dl, u in links[v]:
                if dl > ct and dl + visited_bwd[u] == lt:
                    r = counts_fwd[v] * counts_bwd[u]
                    shortest_count += r
                    shortest_count %= MOD
                    collision_count += pow(r, 2, MOD)
                    collision_count %= MOD

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [[] for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    u -= 1
    v -= 1
    links[u].append((d, v))
    links[v].append((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    dists = [(d, v) for v, d in enumerate(visited) if d != INF]
    dists.sort()
    for dv, v in dists:
        for du, u in links[v]:
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return dists, counts


def solve(s, t, links):
    q = [(0, s, 0), (0, t, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    limit = 0
    while q:
        cost, v, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        pre_cost = visited_self[v]
        if pre_cost == INF:
            visited_self[v] = cost
        elif cost > pre_cost:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            break

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, is_bwd))

    while q:
        cost, v, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if cost < visited_self[v]:
            visited_self[v] = cost

    dists_fwd, counts_fwd = count_routes(visited_fwd, s, links)
    dists_bwd, counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    collision_time = limit / 2
    for d_fwd, v in dists_fwd[:bisect(dists_fwd, (collision_time, n))]:
        d_bwd = visited_bwd[v]
        if d_fwd == d_bwd:
            r = counts_fwd[v] * counts_bwd[v] % MOD
            shortest_count += r
            shortest_count %= MOD
            collision_count += pow(r, 2, MOD)
            collision_count %= MOD
        else:
            ct = collision_time - d_fwd
            lt = limit - d_fwd
            for dl, u in links[v]:
                if dl > ct and dl + visited_bwd[u] == lt:
                    r = counts_fwd[v] * counts_bwd[u] % MOD
                    shortest_count += r
                    shortest_count %= MOD
                    collision_count += pow(r, 2, MOD)
                    collision_count %= MOD

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [[] for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    u -= 1
    v -= 1
    links[u].append((d, v))
    links[v].append((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    dists = [(d, v) for v, d in enumerate(visited) if d != INF]
    dists.sort()
    for dv, v in dists:
        for du, u in links[v]:
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return dists, counts


def solve(s, t, links):
    q = [(0, s, 0), (0, t, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    limit = 0
    while q:
        cost, v, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        pre_cost = visited_self[v]
        if pre_cost == INF:
            visited_self[v] = cost
        elif cost > pre_cost:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            break

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, is_bwd))

    while q:
        cost, v, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if cost < visited_self[v]:
            visited_self[v] = cost

    dists_fwd, counts_fwd = count_routes(visited_fwd, s, links)
    dists_bwd, counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    collision_time = limit / 2
    for d_fwd, v in dists_fwd[:bisect(dists_fwd, (collision_time, n))]:
        d_bwd = visited_bwd[v]
        if d_fwd == d_bwd:
            r = counts_fwd[v] * counts_bwd[v] % MOD
            shortest_count += r
            shortest_count %= MOD
            collision_count += pow(r, 2, MOD)
            collision_count %= MOD
        else:
            ct = collision_time - d_fwd
            lt = limit - d_fwd
            for dl, u in links[v]:
                if dl > ct and dl + visited_bwd[u] == lt:
                    r = counts_fwd[v] * counts_bwd[u] % MOD
                    shortest_count += r
                    shortest_count %= MOD
                    collision_count += pow(r, 2, MOD)
                    collision_count %= MOD

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, sys.stdin.readline().split())
s, t = map(int, sys.stdin.readline().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    dists = [(d, v) for v, d in enumerate(visited) if d != INF]
    dists.sort()
    for dv, v in dists:
        for du, u in links[v]:
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return dists, counts


def solve(s, t, links):
    q = [(0, s, 0), (0, t, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    limit = 0
    while q:
        cost, v, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        pre_cost = visited_self[v]
        if pre_cost == INF:
            visited_self[v] = cost
        elif cost > pre_cost:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            break

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, is_bwd))

    while q:
        cost, v, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if cost < visited_self[v]:
            visited_self[v] = cost

    dists_fwd, counts_fwd = count_routes(visited_fwd, s, links)
    dists_bwd, counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    collision_time = limit / 2
    for d_fwd, v in dists_fwd[:bisect(dists_fwd, (collision_time, n))]:
        d_bwd = visited_bwd[v]
        if d_fwd == d_bwd:
            r = counts_fwd[v] * counts_bwd[v] % MOD
            shortest_count += r
            shortest_count %= MOD
            collision_count += pow(r, 2, MOD)
            collision_count %= MOD
        else:
            ct = collision_time - d_fwd
            lt = limit - d_fwd
            for dl, u in links[v]:
                if dl > ct and dl + visited_bwd[u] == lt:
                    r = counts_fwd[v] * counts_bwd[u] % MOD
                    shortest_count += r
                    shortest_count %= MOD
                    collision_count += pow(r, 2, MOD)
                    collision_count %= MOD

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, sys.stdin.readline().split())
s, t = map(int, sys.stdin.readline().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
from heapq import heappop, heappush

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    dists = [(d, v) for v, d in enumerate(visited) if d != INF]
    dists.sort()
    for dv, v in dists:
        for du, u in links[v]:
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return dists, counts


def solve(s, t, links):
    q = [(0, s, 0), (0, t, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    limit = 0
    while q:
        cost, v, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        pre_cost = visited_self[v]
        if pre_cost == INF:
            visited_self[v] = cost
        elif cost > pre_cost:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            break

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, is_bwd))

    while q:
        cost, v, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if cost < visited_self[v]:
            visited_self[v] = cost

    dists_fwd, counts_fwd = count_routes(visited_fwd, s, links)
    dists_bwd, counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    collision_time = limit / 2
    for d_fwd, v in dists_fwd[:bisect(dists_fwd, (collision_time, n))]:
        d_bwd = visited_bwd[v]
        if d_fwd == d_bwd:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += pow(r, 2, MOD)
            collision_count %= MOD
        else:
            ct = collision_time - d_fwd
            lt = limit - d_fwd
            for dl, u in links[v]:
                if dl > ct and dl + visited_bwd[u] == lt:
                    r = counts_fwd[v] * counts_bwd[u]
                    shortest_count += r
                    shortest_count %= MOD
                    collision_count += pow(r, 2, MOD)
                    collision_count %= MOD

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
from heapq import heappop, heappush


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited_fwd, visited_bwd = [float('inf')] * n, [float('inf')] * n
    pattern_fwd, pattern_bwd = [0] * n, [0] * n
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            pattern_self = pattern_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            pattern_self = pattern_fwd
        if visited_self[v] < cost:
            continue
        visited_self[v] = cost
        pattern_self[v] += 1

        cost_opp = visited_opp[v]
        if cost_opp < INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_pairs.add((v, a) if is_bwd else (a, v))
            break

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, v, is_bwd))

    q.sort()
    for cost, v, a, is_bwd in q[:bisect(q, (limit, n))]:
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            pattern_self = pattern_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            pattern_self = pattern_fwd

        if visited_self[v] < cost:
            continue
        visited_self[v] = cost
        pattern_self[v] += 1

        cost_opp = visited_opp[v]
        if cost_opp < INF:
            if limit < cost + cost_opp or a in collision_nodes:
                continue
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_pairs.add((v, a) if is_bwd else (a, v))

    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = pattern_fwd[v], pattern_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
    collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = pattern_fwd[u], pattern_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited_fwd, visited_bwd = [float('inf')] * n, [float('inf')] * n
    patterns_fwd, patterns_bwd = [0] * n, [0] * n
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            patterns_self = patterns_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            patterns_self = patterns_fwd

        if visited_self[v] < cost:
            continue

        visited_self[v] = cost
        patterns_self[v] += 1

        cost_opp = visited_opp[v]
        if cost_opp < INF:
            if limit < cost + cost_opp or a in collision_nodes:
                break
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        for du, u in links[v]:
            nc = cost + du
            if nc * 2 > limit or visited_self[u] < nc:
                continue
            heappush(q, (nc, u, v, is_bwd))

    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            patterns_self = patterns_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            patterns_self = patterns_fwd

        if visited_self[v] < cost:
            continue
        visited_self[v] = cost
        patterns_self[v] += 1

        cost_opp = visited_opp[v]
        if cost_opp < INF:
            if limit < cost + cost_opp or a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_pairs.add((v, a) if is_bwd else (a, v))

    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = patterns_fwd[v], patterns_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
    collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = patterns_fwd[u], patterns_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited_fwd, visited_bwd = [float('inf')] * n, [float('inf')] * n
    patterns_fwd, patterns_bwd = [0] * n, [0] * n
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
            patterns_self = patterns_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            patterns_self = patterns_fwd

        if visited_self[v] < cost:
            continue

        visited_self[v] = cost
        patterns_self[v] += 1

        cost_opp = visited_opp[v]
        if cost_opp < INF:
            if limit < cost + cost_opp:
                continue
            if a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_nodes.add(v)
            else:
                # print('add', v, a)
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        if cost * 2 <= limit:
            for du, u in links[v]:
                nc = cost + du
                if nc * 2 > limit or visited_self[u] < nc:
                    continue
                heappush(q, (nc, u, v, is_bwd))

    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = patterns_fwd[v], patterns_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
    collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = patterns_fwd[u], patterns_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited = [[float('inf')] * n, [float('inf')] * n]
    patterns = [[0] * n, [0] * n]
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        visited_self = visited[is_bwd]
        if visited_self[v] < cost:
            continue

        visited_self[v] = cost
        patterns[is_bwd][v] += 1

        cost_opp = visited[is_bwd ^ 1][v]
        if cost_opp < INF:
            if limit < cost + cost_opp:
                continue
            if a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_nodes.add(v)
            else:
                # print('add', v, a)
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        if cost * 2 <= limit:
            for du, u in links[v]:
                nc = cost + du
                if nc * 2 > limit or visited_self[u] < nc:
                    continue
                heappush(q, (nc, u, v, is_bwd))

    patterns_fwd, patterns_bwd = patterns
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = patterns_fwd[v], patterns_bwd[v]
        shortest_count += r1 * r2
        collision_count += pow(r1 * r2, 2, MOD)
    shortest_count %= MOD
    collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = patterns_fwd[u], patterns_bwd[v]
        shortest_count += r1 * r2
        collision_count += pow(r1 * r2, 2, MOD)
    # print(limit)
    # print(visited)
    # print(ancestors)
    # print(collision_nodes)
    # print(collision_pairs)
    # print(collision_count, shortest_count)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited = [[float('inf')] * n, [float('inf')] * n]
    patterns = [[0] * n, [0] * n]
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited[is_bwd]
        # print(is_bwd, cost, v, a, visited_self)
        if visited_self[v] < cost:
            continue

        visited_self[v] = cost
        patterns[is_bwd][v] += 1

        cost_opp = visited[is_bwd ^ 1][v]
        if cost_opp < INF:
            if limit < cost + cost_opp:
                continue
            if a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_nodes.add(v)
            else:
                # print('add', v, a)
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        if cost * 2 <= limit:
            for du, u in links[v]:
                nc = cost + du
                if nc * 2 > limit or visited_self[u] < nc:
                    continue
                heappush(q, (nc, u, v, is_bwd))

    patterns_fwd, patterns_bwd = patterns
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = patterns_fwd[v], patterns_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = patterns_fwd[u], patterns_bwd[v]
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    # print(limit)
    # print(visited)
    # print(ancestors)
    # print(collision_nodes)
    # print(collision_pairs)
    # print(collision_count, shortest_count)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def get_patterns_func(s, ancestors):
    cache = {s: 1}

    def get_patterns(v):
        if v in cache:
            return cache[v]
        return sum(get_patterns(a) for a in ancestors[v])

    return get_patterns


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited = [[float('inf')] * n, [float('inf')] * n]
    ancestors = [[set() for _ in range(n)], [set() for _ in range(n)]]
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited[is_bwd]
        # print(is_bwd, cost, v, a, visited_self)
        if visited_self[v] < cost:
            continue

        visited_self[v] = cost
        ancestors[is_bwd][v].add(a)

        cost_opp = visited[is_bwd ^ 1][v]
        if cost_opp < INF:
            if limit < cost + cost_opp:
                continue
            if a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_nodes.add(v)
            else:
                # print('add', v, a)
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        if cost * 2 <= limit:
            for du, u in links[v]:
                nc = cost + du
                if nc * 2 > limit or visited_self[u] < nc:
                    continue
                heappush(q, (nc, u, v, is_bwd))

    get_patterns_fwd = get_patterns_func(s, ancestors[0])
    get_patterns_bwd = get_patterns_func(t, ancestors[1])
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = get_patterns_fwd(v), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = get_patterns_fwd(u), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    # print(limit)
    # print(visited)
    # print(ancestors)
    # print(collision_nodes)
    # print(collision_pairs)
    # print(collision_count, shortest_count)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def get_patterns_func(s, ancestors):
    cache = {s: 1}

    def get_patterns(v):
        if v in cache:
            return cache[v]
        return sum(get_patterns(a) for a in ancestors[v])

    return get_patterns


def solve(s, t, links):
    MOD, INF = 1000000007, float('inf')
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited = [[float('inf')] * n, [float('inf')] * n]
    ancestors = [[set() for _ in range(n)], [set() for _ in range(n)]]
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited[is_bwd]
        # print(is_bwd, cost, v, a, visited_self)
        if visited_self[v] < cost:
            continue

        visited_self[v] = cost
        ancestors[is_bwd][v].add(a)

        cost_opp = visited[is_bwd ^ 1][v]
        if cost_opp < INF:
            if limit < cost + cost_opp:
                continue
            if a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_nodes.add(v)
            else:
                # print('add', v, a)
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        for du, u in links[v]:
            nc = cost + du
            if visited_self[u] < nc:
                continue
            heappush(q, (nc, u, v, is_bwd))

    get_patterns_fwd = get_patterns_func(s, ancestors[0])
    get_patterns_bwd = get_patterns_func(t, ancestors[1])
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = get_patterns_fwd(v), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = get_patterns_fwd(u), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    # print(limit)
    # print(visited)
    # print(ancestors)
    # print(collision_pair)
    # print(collision_count, shortest_count)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush


def get_patterns_func(s, ancestors):
    cache = {s: 1}

    def get_patterns(v):
        if v in cache:
            return cache[v]
        return sum(get_patterns(a) for a in ancestors[v])

    return get_patterns


def solve(s, t, links):
    MOD = 1000000007
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited = [{}, {}]
    ancestors = [defaultdict(set), defaultdict(set)]
    limit = float('inf')
    collision_nodes = set()
    collision_pairs = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited[is_bwd]
        # print(is_bwd, cost, v, a, visited_self)
        if v in visited_self and visited_self[v] < cost:
            continue

        visited_self[v] = cost
        ancestors[is_bwd][v].add(a)

        visited_opp = visited[is_bwd ^ 1]
        if v in visited_opp:
            cost_opp = visited_opp[v]
            if limit < cost + cost_opp:
                continue
            if a in collision_nodes:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_nodes.add(v)
            else:
                # print('add', v, a)
                collision_pairs.add((v, a) if is_bwd else (a, v))
            continue

        for du, u in links[v]:
            nc = cost + du
            if u in visited_self and visited_self[u] < nc:
                continue
            heappush(q, (nc, u, v, is_bwd))

    get_patterns_fwd = get_patterns_func(s, ancestors[0])
    get_patterns_bwd = get_patterns_func(t, ancestors[1])
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        r1, r2 = get_patterns_fwd(v), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    for u, v in collision_pairs:
        r1, r2 = get_patterns_fwd(u), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    # print(limit)
    # print(visited)
    # print(ancestors)
    # print(collision_pair)
    # print(collision_count, shortest_count)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush


def get_patterns_func(s, ancestors):
    cache = {s: 1}

    def get_patterns(v):
        if v in cache:
            return cache[v]
        return sum(get_patterns(a) for a in ancestors[v])

    return get_patterns


def solve(s, t, links):
    MOD = 1000000007
    q = [(0, s, -1, 0), (0, t, -1, 1)]
    visited = [{}, {}]
    ancestors = [defaultdict(set), defaultdict(set)]
    limit = float('inf')
    collision_pair = set()
    while q:
        cost, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited[is_bwd]
        # print(is_bwd, cost, v, a, visited_self)
        if v in visited_self and visited_self[v] < cost:
            continue

        visited_self[v] = cost
        ancestors[is_bwd][v].add(a)

        visited_opp = visited[is_bwd ^ 1]
        if v in visited_opp:
            cost_opp = visited_opp[v]
            if limit < cost + cost_opp:
                continue
            if (a, a) in collision_pair:
                continue
            limit = cost + cost_opp
            if cost == cost_opp:
                # print('add', v)
                collision_pair.add((v, v))
            else:
                # print('add', v, a)
                collision_pair.add((v, a) if is_bwd else (a, v))
            continue

        for du, u in links[v]:
            nc = cost + du
            if u in visited_self and visited_self[u] < nc:
                continue
            heappush(q, (nc, u, v, is_bwd))

    get_patterns_fwd = get_patterns_func(s, ancestors[0])
    get_patterns_bwd = get_patterns_func(t, ancestors[1])
    shortest_count = 0
    collision_count = 0

    for u, v in collision_pair:
        r1, r2 = get_patterns_fwd(u), get_patterns_bwd(v)
        shortest_count += r1 * r2
        shortest_count %= MOD
        collision_count += pow(r1 * r2, 2, MOD)
        collision_count %= MOD
    # print(limit)
    # print(visited)
    # print(ancestors)
    # print(collision_pair)
    # print(collision_count, shortest_count)

    return (pow(shortest_count, 2, MOD) - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = defaultdict(set)
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def backward_search(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] ** 2 * patterns_b[d] ** 2
            collision %= 1000000007
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = backward_search(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return (pow(pt, 2, 1000000007) - collision) % 1000000007


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            collision %= 1000000007
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return (pow(pt, 2, 1000000007) - collision) % 1000000007


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            collision %= 1000000007
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return (pow(pt, 2, 1000000007) - collision) % 1000000007


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[v] < cost:
            if visited[t] < cost:
                break
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[v] < cost:
            if v == t:
                break
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[v] < cost:
            if v == t:
                break
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = [(t, -1)]
    while q:
        v, d = heappop(q)
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        for a in ancestors[v]:
            heappush(q, (a, v))
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))


Fixed submission:
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))