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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    inf = 10 ** 15
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, d])
        to[v].append([u, d])

    # sからのダイクストラで
    # 各頂点までの最短距離dists
    # sからのルート数way_s
    # 逆向きのダグot
    # 以上を作る
    dists = [inf] * n
    way_s = [0] * n
    ot = defaultdict(list)
    hp = []
    heappush(hp, [0, s])
    way_s[s] = 1
    u = -1
    while u != t:
        dist, u = heappop(hp)
        if dists[u] != inf: continue
        dists[u] = dist
        for v, d in to[u]:
            if dists[v] == inf:
                heappush(hp, [dist + d, v])
            elif dists[v] == dist - d:
                way_s[u] += way_s[v]
                ot[u].append(v)
    #print(dists)
    #print(way_s)
    #print(ot)

    # tからのbfsで
    # sからのルート数way_tを作りながら
    # 衝突するルート数way_colを計算していく
    way_t = [0] * n
    way_col = 0
    half = dists[t] / 2
    way_t[t] = 1
    hp = []
    heappush(hp, [-dists[t], t])
    while hp:
        dist, u = heappop(hp)
        if -dist == half:
            way_col += pow(way_t[u] * way_s[u], 2, md)
            way_col %= md
            continue
        way = way_t[u]
        for v in ot[u]:
            if dists[v] < half:
                way_col += pow(way_t[u] * way_s[v], 2, md)
                way_col %= md
            else:
                way_t[v] += way
                heappush(hp, [-dists[v], v])
    #print(way_col)

    # 全ルートから衝突するルートを引いて答え
    ans = pow(way_s[t], 2, md) - way_col
    ans %= md
    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    inf = 10 ** 15
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, d])
        to[v].append([u, d])

    # sからのダイクストラで
    # 各頂点までの最短距離dists
    # sからのルート数way_s
    # 逆向きのダグot
    # 以上を作る
    dists = [inf] * n
    way_s = [0] * n
    ot = defaultdict(list)
    hp = []
    heappush(hp, [0, s])
    way_s[s] = 1
    u = -1
    while u != t:
        dist, u = heappop(hp)
        if dists[u] != inf: continue
        dists[u] = dist
        for v, d in to[u]:
            if dists[v] == inf:
                heappush(hp, [dist + d, v])
            elif dists[v] == dist - d:
                way_s[u] += way_s[v]
                ot[u].append(v)
    #print(dists)
    #print(way_s)
    #print(ot)

    # tからのbfsで
    # sからのルート数way_tを作りながら
    # 衝突するルート数way_colを計算していく
    way_t = [0] * n
    way_col = 0
    half = dists[t] / 2
    way_t[t] = 1
    hp = []
    heappush(hp, [-dists[t], t])
    while hp:
        dist, u = heappop(hp)
        if -dist == half:
            way_col += pow(way_t[u] * way_s[u], 2, md)
            way_col %= md
            continue
        way = way_t[u]
        for v in ot[u]:
            if dists[v] < half:
                way_col += pow(way_t[u] * way_s[v], 2, md)
                way_col %= md
            else:
                way_t[v] += way
                heappush(hp, [-dists[v], v])
    #print(way_col)

    # 全ルートから衝突するルートを引いて答え
    ans = pow(way_s[t], 2, md) - way_col
    ans %= md
    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    inf = 10 ** 15
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, d])
        to[v].append([u, d])

    # sからのダイクストラで
    # 各頂点までの最短距離dists
    # sからのルート数way_s
    # 逆向きのダグot
    # 以上を作る
    dists = [inf] * n
    way_s = [0] * n
    ot = defaultdict(list)
    hp = []
    heappush(hp, [0, s])
    way_s[s] = 1
    u = -1
    while u != t:
        dist, u = heappop(hp)
        if dists[u] != inf: continue
        dists[u] = dist
        for v, d in to[u]:
            if dists[v] == inf:
                heappush(hp, [dist + d, v])
            elif dists[v] == dist - d:
                way_s[u] += way_s[v]
                ot[u].append(v)
    #print(dists)
    #print(way_s)
    #print(ot)

    # tからのbfsで
    # sからのルート数way_tを作りながら
    # 衝突するルート数way_colを計算していく
    way_t = [0] * n
    way_col = 0
    half = dists[t] / 2
    way_t[t] = 1
    hp = []
    heappush(hp, [-dists[t], t])
    while hp:
        dist, u = heappop(hp)
        if -dist == half:
            way_col += pow(way_t[u] * way_s[u], 2, md)
            way_col %= md
            continue
        way = way_t[u]
        for v in ot[u]:
            if dists[v] < half:
                way_col += pow(way_t[u] * way_s[v], 2, md)
                way_col %= md
            else:
                way_t[v] += way
                heappush(hp, [-dists[v], v])
    #print(way_col)

    # 全ルートから衝突するルートを引いて答え
    ans = pow(way_s[t], 2, md) - way_col
    ans %= md
    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    ee = []
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, d])
        to[v].append([u, d])
        ee.append([u, v, d])

    # 各頂点までの最短距離distsを作る
    hp = []
    heappush(hp, [0, s])
    dists = [-1] * n
    dist_greater_u = []
    while hp:
        dist, u = heappop(hp)
        if dists[u] != -1: continue
        dists[u] = dist
        dist_greater_u.append(u)
        for v, d in to[u]:
            if dists[v] != -1: continue
            heappush(hp, [dist + d, v])
    # print(dists)

    # sからのs_dag、tからのt_dagを作る
    dag_s = defaultdict(list)
    dag_t = defaultdict(list)
    for u, v, d in ee:
        if dists[u] + d == dists[v]:
            dag_s[u].append(v)
            dag_t[v].append(u)
        if dists[v] + d == dists[u]:
            dag_s[v].append(u)
            dag_t[u].append(v)
    # print(dag_s)
    # print(dag_t)

    # sから各頂点までのルート数way_sとtからのway_tを作る
    way_s = [0] * n
    way_t = [0] * n
    way_s[s] = 1
    for u in dist_greater_u:
        way = way_s[u]
        for v in dag_s[u]:
            way_s[v] += way
    way_t[t] = 1
    for u in dist_greater_u[::-1]:
        way = way_t[u]
        for v in dag_t[u]:
            way_t[v] += way
    # print(way_s)
    # print(way_t)

    # 衝突するルートを数える
    half = dists[t] / 2
    cnt_col = 0
    for u in range(n):
        du = dists[u]
        if du == half:
            cnt_col += pow(way_s[u] * way_t[u], 2, md)
        elif du < half:
            for v in dag_s[u]:
                if dists[v] > half:
                    cnt_col += pow(way_s[u] * way_t[v], 2, md)

    # 全ルートから衝突するルートを引いて答え
    print((way_s[t] ** 2 - cnt_col) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    ee = []
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, d])
        to[v].append([u, d])
        ee.append([u, v, d])

    # 各頂点までの最短距離distsを作る
    hp = []
    heappush(hp, [0, s])
    dists = [-1] * n
    dist_greater_u = []
    while hp:
        dist, u = heappop(hp)
        if dists[u] != -1: continue
        dists[u] = dist
        dist_greater_u.append(u)
        for v, d in to[u]:
            if dists[v] != -1: continue
            heappush(hp, [dist + d, v])
    # print(dists)

    # sからのs_dag、tからのt_dagを作る
    dag_s = defaultdict(list)
    dag_t = defaultdict(list)
    for u, v, d in ee:
        if dists[u] + d == dists[v]:
            dag_s[u].append(v)
            dag_t[v].append(u)
        if dists[v] + d == dists[u]:
            dag_s[v].append(u)
            dag_t[u].append(v)
    # print(dag_s)
    # print(dag_t)

    # sから各頂点までのルート数way_sとtからのway_tを作る
    way_s = [0] * n
    way_t = [0] * n
    way_s[s] = 1
    for u in dist_greater_u:
        way = way_s[u]
        for v in dag_s[u]:
            way_s[v] += way
    way_t[t] = 1
    for u in dist_greater_u[::-1]:
        way = way_t[u]
        for v in dag_t[u]:
            way_t[v] += way
    # print(way_s)
    # print(way_t)

    # 衝突するルートを数える
    half = dists[t] / 2
    cnt_col = 0
    for u in range(n):
        du = dists[u]
        if du == half:
            cnt_col += pow(way_s[u] * way_t[u], 2, md)
        elif du < half:
            for v in dag_s[u]:
                if dists[v] > half:
                    cnt_col += pow(way_s[u] * way_t[v], 2, md)

    # 全ルートから衝突するルートを引いて答え
    print((way_s[t] ** 2 - cnt_col) % md)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    uv_to_ei = {}
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        uv_to_ei[(u, v)] = uv_to_ei[(v, u)] = ei
        to[u].append([v, d])
        to[v].append([u, d])
    hp = []
    heappush(hp, [0, s])
    while hp:
        dist, u = heappop(hp)
        if u == t:
            min_dist = dist
            break
        for v, d in to[u]:
            heappush(hp, [dist + d, v])
    # print(min_dist)
    half = min_dist / 2
    dists = [-1] * n
    hp = []
    heappush(hp, [0, s, -1, 1])
    ways = defaultdict(int)
    while hp:
        dist, u, h0, way = heappop(hp)
        if u == t and dist == min_dist:
            ways[h0] += way
            continue
        if dists[u] == -1: dists[u] = dist
        if dists[u] != dist: continue
        for v, d in to[u]:
            nd = dist + d
            if nd == half:
                h0 = v
            elif dist < half < nd:
                h0 = uv_to_ei[(u, v)] + n
            heappush(hp, [dist + d, v, h0, way])
    # print(uv_to_ei)
    # print(ways)
    sum_v = 0
    sum_v2 = 0
    for k, v in ways.items():
        sum_v += v
        sum_v2 += v ** 2
    print(sum_v ** 2 - sum_v2)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()