AtCoder Regular Contest 090 - Avoiding Collision

We have a graph with N vertices and M edges, and there are two people on the graph: Takahashi and Aoki.
The i-th edge connects Vertex U_i and Vertex V_i.
The time it takes to traverse this edge is D_i minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).
Takahashi departs Vertex S and Aoki departs Vertex T at the same time. Takahashi travels to Vertex T and Aoki travels to Vertex S, both in the shortest time possible.
Find the number of the pairs of ways for Takahashi and Aoki to choose their shortest paths such that they never meet (at a vertex or on an edge) during the travel, modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq N \leq 100 000
 - 1 \leq M \leq 200 000
 - 1 \leq S, T \leq N
 - S \neq T
 - 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
 - 1 \leq D_i \leq 10^9 (1 \leq i \leq M)
 - If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).
 - U_i \neq V_i (1 \leq i \leq M)
 - D_i are integers.
 - The given graph is connected.

-----Input-----
Input is given from Standard Input in the following format:
N M
S T
U_1 V_1 D_1
U_2 V_2 D_2
:
U_M V_M D_M

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

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

-----Sample Output-----
2

There are two ways to choose shortest paths that satisfies the condition:
 - Takahashi chooses the path 1 \rightarrow 2 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 4 \rightarrow 1.
 - Takahashi chooses the path 1 \rightarrow 4 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 2 \rightarrow 1.

Difficulty: HARD

Starter code:

Solutions:
from heapq import heappush, heappop

def dijkstra(s):
	a = [1 << 50] * N
	a[s] = 0
	p = [(0, s)]
	while p:
		(d, v) = heappop(p)
		if d > a[v]:
			continue
		for (u, w) in G[v]:
			if a[u] > d + w:
				a[u] = d + w
				heappush(p, (d + w, u))
	return a

def cnt(dist, s):
	w = [0] * N
	w[s] = 1
	b = [0] * N
	b[s] = 1
	p = [(0, s)]
	while p:
		(d, v) = heappop(p)
		for (u, d) in G[v]:
			if dist[v] + d == dist[u]:
				w[u] = (w[u] + w[v]) % m
				if not b[u]:
					heappush(p, (dist[u], u))
					b[u] = 1
	return w
m = 10 ** 9 + 7
(N, M) = map(int, input().split())
(S, T) = map(int, input().split())
S -= 1
T -= 1
G = [[] for _ in [0] * N]
for _ in [0] * M:
	(U, V, D) = map(int, input().split())
	U -= 1
	V -= 1
	G[U] += [(V, D)]
	G[V] += [(U, D)]
dS = dijkstra(S)
dT = dijkstra(T)
wS = cnt(dS, S)
wT = cnt(dT, T)
s = dS[T]
a = wS[T] ** 2 % m
if s % 2 == 0:
	for i in range(N):
		if dS[i] == dT[i] == s // 2:
			a = (a - (wS[i] * wT[i]) ** 2) % m
for i in range(N):
	for (j, d) in G[i]:
		if dS[i] + d + dT[j] == s:
			if dS[i] < dT[i] and dT[j] < dS[j]:
				a = (a - (wS[i] * wT[j]) ** 2) % m
print(a)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 15

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, m) = LI()
(s, t) = LI()
G = [[] for _ in range(n)]
for i in range(m):
	(a, b, c) = LI()
	G[a - 1] += [(b - 1, c)]
	G[b - 1] += [(a - 1, c)]

def dijkstra(graph, start=0):
	route_cnt = [start] * n
	route_cnt[start] = 1
	que = [(0, start)]
	dist = [INF] * n
	dist[start] = 0
	while que:
		(min_dist, u) = heappop(que)
		if min_dist > dist[u]:
			continue
		for (v, c) in graph[u]:
			if dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				route_cnt[v] = route_cnt[u]
				heappush(que, (dist[u] + c, v))
			elif dist[u] + c == dist[v]:
				route_cnt[v] = (route_cnt[v] + route_cnt[u]) % mod
	return (route_cnt, dist)
(route_cnt, dist) = dijkstra(G, s - 1)
(r_route_cnt, r_dist) = dijkstra(G, t - 1)
total_dist = dist[t - 1]
ret = 0
for i in range(n):
	if dist[i] == r_dist[i]:
		ret = ret + (route_cnt[i] * r_route_cnt[i] % mod) ** 2 % mod
for u in range(n):
	for (v, c) in G[u]:
		if dist[u] < total_dist / 2 < dist[v] and dist[u] + c + r_dist[v] == total_dist:
			ret = (ret + route_cnt[u] ** 2 % mod * r_route_cnt[v] ** 2 % mod) % mod
print((route_cnt[t - 1] ** 2 - ret) % mod)


import sys

def MI():
	return map(int, sys.stdin.readline().rstrip().split())
(N, M) = MI()
(S, T) = MI()
edges = [[] for _ in range(N + 1)]
edges2 = []
for _ in range(M):
	(U, V, D) = MI()
	edges[U].append((V, D))
	edges[V].append((U, D))
	edges2.append((U, V, D))
	edges2.append((V, U, D))
mod = 10 ** 9 + 7
from heapq import heappop, heappush
distS = [(10 ** 18, 0)] * (N + 1)
distS[S] = (0, 1)
qS = []
heappush(qS, (0, S))
vS = [False] * (N + 1)
while qS:
	(d, i) = heappop(qS)
	if vS[i]:
		continue
	vS[i] = True
	for (j, d) in edges[i]:
		if vS[j]:
			continue
		if distS[j][0] > distS[i][0] + d:
			distS[j] = (distS[i][0] + d, distS[i][1])
			heappush(qS, (distS[i][0] + d, j))
		elif distS[j][0] == distS[i][0] + d:
			distS[j] = (distS[j][0], distS[j][1] + distS[i][1])
			heappush(qS, (distS[i][0] + d, j))
distT = [(10 ** 18, 0)] * (N + 1)
distT[T] = (0, 1)
qT = []
heappush(qT, (0, T))
vT = [False] * (N + 1)
while qT:
	(d, i) = heappop(qT)
	if vT[i]:
		continue
	vT[i] = True
	for (j, d) in edges[i]:
		if vT[j]:
			continue
		if distT[j][0] > distT[i][0] + d:
			distT[j] = (distT[i][0] + d, distT[i][1])
			heappush(qT, (distT[i][0] + d, j))
		elif distT[j][0] == distT[i][0] + d:
			distT[j] = (distT[j][0], distT[j][1] + distT[i][1])
			heappush(qT, (distT[i][0] + d, j))
(a, b) = distS[T]
ans = b ** 2 % mod
if a % 2 == 0:
	for i in range(1, N + 1):
		if distS[i][0] == distT[i][0] == a // 2:
			ans -= (distS[i][1] * distT[i][1]) ** 2
			ans %= mod
for i in range(2 * M):
	(U, V, D) = edges2[i]
	if distS[U][0] < (a + 1) // 2 and distT[V][0] < (a + 1) // 2 and (a == distS[U][0] + D + distT[V][0]):
		ans -= (distS[U][1] * distT[V][1]) ** 2
		ans %= mod
print(ans)


import sys
input = sys.stdin.readline
import heapq as hq
(n, m) = map(int, input().split())
(s, t) = map(int, input().split())
abd = [list(map(int, input().split())) for i in range(m)]
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for (a, b, d) in abd:
	graph[a].append((b, d))
	graph[b].append((a, d))
dists = [[10 ** 18, 0] for i in range(n + 1)]
distt = [[10 ** 18, 0] for i in range(n + 1)]
for (start, dist) in ((s, dists), (t, distt)):
	dist[start] = [0, 1]
	q = [(0, start)]
	hq.heapify(q)
	while q:
		(dx, x) = hq.heappop(q)
		k = dist[x][1]
		for (y, d) in graph[x]:
			if dist[y][0] > dx + d:
				dist[y][0] = dx + d
				dist[y][1] = k
				hq.heappush(q, (dist[y][0], y))
			elif dist[y][0] == dx + d:
				dist[y][1] = (dist[y][1] + k) % mod
dst = dists[t][0]
ans = dists[t][1] ** 2 % mod
for v in range(1, n + 1):
	if dists[v][0] + distt[v][0] != dst:
		continue
	if dists[v][0] * 2 == distt[v][0] * 2 == dst:
		ans = (ans - (dists[v][1] * distt[v][1]) ** 2) % mod
	else:
		for (u, d) in graph[v]:
			if dists[u][0] * 2 < dst and distt[v][0] * 2 < dst:
				if dists[u][0] + distt[v][0] + d == dst:
					ans = (ans - (dists[u][1] * distt[v][1]) ** 2) % mod
print(ans % mod)


import heapq as h

def f(s):
	a = [1 << 50] * N
	a[s] = 0
	p = [(0, s)]
	c = [0] * N
	c[s] = 1
	while p:
		(d, v) = h.heappop(p)
		if d <= a[v]:
			for (u, w) in G[v]:
				if a[u] > d + w:
					a[u] = d + w
					h.heappush(p, (d + w, u))
					c[u] = 0
				if a[u] == d + w:
					c[u] += c[v]
	return (a, c)
n = lambda : map(int, input().split())
(N, M) = n()
N += 1
(S, T) = n()
G = [[] for _ in [0] * N]
for _ in [0] * M:
	(U, V, D) = n()
	G[U] += [(V, D)]
	G[V] += [(U, D)]
(P, X) = f(S)
(Q, Y) = f(T)
s = P[T]
print((X[T] ** 2 - (1 - s % 2) * sum(((X[i] * Y[i]) ** 2 for i in range(N) if P[i] == Q[i] == s // 2)) - sum(((P[i] + d + Q[j] == s) * (P[i] < Q[i]) * (Q[j] < P[j]) * (X[i] * Y[j]) ** 2 for i in range(N) for (j, d) in G[i]))) % (10 ** 9 + 7))


import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp

def dijkstra(N, s, Edge):
	inf = geta
	dist = [inf] * N
	dist[s] = 0
	Q = [(0, s)]
	dp = [0] * N
	dp[s] = 1
	while Q:
		(dn, vn) = hpp(Q)
		if dn > dist[vn]:
			continue
		for (df, vf) in Edge[vn]:
			if dist[vn] + df < dist[vf]:
				dist[vf] = dist[vn] + df
				dp[vf] = dp[vn]
				hp(Q, (dn + df, vf))
			elif dist[vn] + df == dist[vf]:
				dp[vf] = (dp[vf] + dp[vn]) % MOD
	return (dist, dp)
MOD = 10 ** 9 + 7
(N, M) = map(int, readline().split())
(S, T) = map(int, readline().split())
S -= 1
T -= 1
geta = 10 ** 15
Edge = [[] for _ in range(N)]
for _ in range(M):
	(u, v, d) = map(int, readline().split())
	u -= 1
	v -= 1
	Edge[u].append((d, v))
	Edge[v].append((d, u))
(dists, dps) = dijkstra(N, S, Edge)
(distt, dpt) = dijkstra(N, T, Edge)
st = dists[T]
onpath = [i for i in range(N) if dists[i] + distt[i] == st]
ans = dps[T] ** 2 % MOD
for i in onpath:
	if 2 * dists[i] == 2 * distt[i] == st:
		ans = (ans - pow(dps[i] * dpt[i], 2, MOD)) % MOD
	for (cost, vf) in Edge[i]:
		if dists[i] + cost + distt[vf] == st:
			if 2 * dists[i] < st < 2 * dists[vf]:
				ans = (ans - pow(dps[i] * dpt[vf], 2, MOD)) % MOD
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop

def dijkstra(n, E, i0=0):
	kk = 18
	mm = (1 << kk) - 1
	h = [i0]
	D = [-1] * n
	done = [0] * n
	D[i0] = 0
	while h:
		x = hpop(h)
		(d, i) = (x >> kk, x & mm)
		if done[i]:
			continue
		done[i] = 1
		for (j, w) in E[i]:
			nd = d + w
			if D[j] < 0 or D[j] > nd:
				if done[j] == 0:
					hpush(h, (nd << kk) + j)
					D[j] = nd
	return D

def dijkstra2(n, DD, i0=0):
	L = [0] * n
	L[i0] = 1
	AA = [i for i in V]
	AA.sort(key=lambda x: DD[x])
	for a in AA:
		for (b, c) in E[a]:
			if DD[b] + c == DD[a]:
				L[a] += L[b]
				if L[a] >= P:
					L[a] -= P
	return L
P = 10 ** 9 + 7
(N, M) = list(map(int, input().split()))
(S, T) = [int(a) - 1 for a in input().split()]
E = [[] for _ in range(N)]
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	E[a - 1].append((b - 1, c))
	E[b - 1].append((a - 1, c))
D1 = dijkstra(N, E, S)
D2 = dijkstra(N, E, T)
mad = D1[T]
V = set([i for i in range(N) if D1[i] + D2[i] == mad])
X = dijkstra2(N, D1, S)
Y = dijkstra2(N, D2, T)
ans = X[T] ** 2 % P
for i in V:
	if D1[i] == D2[i]:
		ans = (ans - (X[i] * Y[i] % P) ** 2) % P
for a in V:
	for (b, c) in E[a]:
		if D1[a] + c == D1[b]:
			if D1[a] * 2 < mad < D1[b] * 2:
				ans = (ans - (X[a] * Y[b] % P) ** 2) % P
print(ans)


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
INF = 10 ** 18
mod = 10 ** 9 + 7

def dijkstra(start, n, graph):
	route_cnt = [start] * n
	route_cnt[start] = 1
	que = [(0, start)]
	dist = [INF] * n
	dist[start] = 0
	while que:
		(min_dist, u) = heappop(que)
		if min_dist > dist[u]:
			continue
		for (c, v) in graph[u]:
			if dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				route_cnt[v] = route_cnt[u]
				heappush(que, (dist[u] + c, v))
			elif dist[u] + c == dist[v]:
				route_cnt[v] = (route_cnt[v] + route_cnt[u]) % mod
	return (route_cnt, dist)
(N, M) = list(map(int, input().split()))
(S, T) = list(map(int, input().split()))
G = [[] for _ in range(N)]
edges = []
for _ in range(M):
	(u, v, d) = list(map(int, input().split()))
	G[u - 1].append((d, v - 1))
	G[v - 1].append((d, u - 1))
	edges.append((v - 1, u - 1, d))
(num_s, dist_s) = dijkstra(S - 1, N, G)
(num_t, dist_t) = dijkstra(T - 1, N, G)
ans = num_s[T - 1] ** 2 % mod
l = dist_s[T - 1]
for (u, v, d) in edges:
	if dist_s[v] < dist_s[u]:
		(u, v) = (v, u)
	if dist_s[u] * 2 < l < dist_s[v] * 2 and dist_s[u] + dist_t[v] + d == l:
		ans -= num_s[u] ** 2 % mod * (num_t[v] ** 2 % mod)
		ans %= mod
for v in range(N):
	if dist_s[v] == dist_t[v] == l / 2:
		ans -= num_t[v] ** 2 % mod * (num_s[v] ** 2 % mod)
		ans %= mod
print(ans % mod)


def examC():
	ans = 0
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():

	def dijkstra(edges, start=0):
		dist = [inf] * len(edges)
		dist[start] = 0
		Q = [(0, start)]
		while Q:
			(d, v) = heapq.heappop(Q)
			if dist[v] < d:
				continue
			for (u, cost) in edges[v]:
				if dist[u] > dist[v] + cost:
					dist[u] = dist[v] + cost
					heapq.heappush(Q, (dist[u], u))
		return dist
	(N, M) = LI()
	(S, T) = LI()
	S -= 1
	T -= 1
	V = [set() for _ in range(N)]
	for _ in range(M):
		(u, v, c) = LI()
		u -= 1
		v -= 1
		V[u].add((v, c))
		V[v].add((u, c))
	distS = dijkstra(V, S)
	distT = dijkstra(V, T)
	L = distS[T]
	numS = [i for i in range(N)]
	C = list(zip(distS, numS))
	C.sort()
	(_, numS) = zip(*C)
	numT = [i for i in range(N)]
	C = list(zip(distT, numT))
	C.sort()
	(_, numT) = zip(*C)
	dp1 = [0] * N
	dp2 = [0] * N
	dp1[S] = 1
	dp2[T] = 1
	S_collision_points = set()
	S_collision_edges = set()
	for now in numS:
		if distS[now] + distT[now] == L and distS[now] == distT[now]:
			S_collision_points.add(now)
		for (v, c) in V[now]:
			if distT[v] + distS[now] == L - c:
				dp1[v] += dp1[now]
				dp1[v] %= mod
				if distS[now] * 2 < L and L < distS[v] * 2:
					S_collision_edges.add((now, v))
	for now in numT:
		for (v, c) in V[now]:
			if distS[v] + distT[now] == L - c:
				dp2[v] += dp2[now]
				dp2[v] %= mod
	collision_points = S_collision_points
	collision_edges = S_collision_edges
	ans = 0
	ans += dp1[T] ** 2
	ans %= mod
	for p in collision_points:
		if distS[p] == distT[p]:
			ans -= dp1[p] ** 2 * dp2[p] ** 2
			ans += supermod
			ans %= mod
	for (u, v) in collision_edges:
		ans -= dp1[u] ** 2 * dp2[v] ** 2
		ans += supermod
		ans %= mod
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
from decimal import getcontext, Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
supermod = mod ** 4
mod2 = 998244353
inf = 10 ** 18
_ep = dec('0.000000000001')
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}
getcontext().prec = 28
sys.setrecursionlimit(10 ** 7)
examE()


import heapq
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
(S, T) = map(lambda x: int(x) - 1, input().split())
adjList = [[] for i in range(N)]
for i in range(M):
	(U, V, D) = map(int, input().split())
	adjList[U - 1].append((V - 1, D))
	adjList[V - 1].append((U - 1, D))
numRouteS = [0 for i in range(N)]
numRouteS[S] = 1
cost = [float('inf')] * N
cost[S] = 0
prev = [None] * N
pq = []
heapq.heappush(pq, (0, S))
vs = []
while pq:
	(c, vNow) = heapq.heappop(pq)
	if c > cost[vNow]:
		continue
	if c > cost[T]:
		break
	vs += [vNow]
	for (v2, wt) in adjList[vNow]:
		c2 = cost[vNow] + wt
		if c2 <= cost[v2]:
			if c2 == cost[v2]:
				prev[v2] += [vNow]
				numRouteS[v2] = (numRouteS[v2] + numRouteS[vNow]) % MOD
			else:
				cost[v2] = c2
				prev[v2] = [vNow]
				numRouteS[v2] = numRouteS[vNow]
				heapq.heappush(pq, (c2, v2))
numRouteT = [0] * N
numRouteT[T] = 1
for v in reversed(vs[1:]):
	for v0 in prev[v]:
		numRouteT[v0] = (numRouteT[v0] + numRouteT[v]) % MOD
cST = cost[T]
ans = numRouteS[T] ** 2 % MOD
for (v, c) in enumerate(cost):
	if c * 2 == cST:
		x = numRouteS[v] ** 2 % MOD
		y = numRouteT[v] ** 2 % MOD
		ans = (ans - x * y) % MOD
for (v, c) in enumerate(cost):
	if c * 2 < cST:
		for (v2, wt) in adjList[v]:
			if cost[v2] * 2 > cST and c + wt == cost[v2]:
				x = numRouteS[v] ** 2 % MOD
				y = numRouteT[v2] ** 2 % MOD
				ans = (ans - x * y) % MOD
print(ans)


from collections import defaultdict
from functools import reduce
import heapq as hq
from sys import stdin
MOD = 10 ** 9 + 7
(N, M) = map(int, stdin.readline().split())
(S, T) = map(int, stdin.readline().split())
(S, T) = (S - 1, T - 1)
E = defaultdict(list)
lines = stdin.readlines()
for line in lines:
	(u, v, d) = map(int, line.split())
	E[u - 1].append((v - 1, d))
	E[v - 1].append((u - 1, d))
dS = [None] * N
dT = [None] * N
Q = [(0, S, False), (0, T, True)]
D = float('inf')
while Q:
	(d, v, f) = hq.heappop(Q)
	if d * 2 > D:
		break
	dM = dT if f else dS
	dN = dS if f else dT
	if dM[v] is None:
		dM[v] = d
		for (u, dd) in E[v]:
			if dM[u] is None and (d + dd) * 2 <= D:
				hq.heappush(Q, (d + dd, u, f))
	if dN[v] is not None:
		D = min(dN[v] + d, D)
del Q

def helper(start, dist):
	cnts = [0] * N
	cnts[start] = 1
	for (d, v) in sorted(((d, v) for (v, d) in enumerate(dist) if d is not None)):
		c = cnts[v]
		for (u, dd) in E[v]:
			if dd + d == dist[u]:
				cnts[u] = (cnts[u] + c) % MOD
	return cnts
Sn = helper(S, dS)
Tn = helper(T, dT)

def it():
	for v in range(N):
		if dS[v] is not None:
			ds = dS[v]
			if dT[v] == ds and ds * 2 == D:
				yield (Sn[v] * Tn[v] % MOD)
			else:
				for (u, d) in E[v]:
					if dT[u] is not None and abs(dT[u] - ds) < d and (ds + d + dT[u] == D):
						yield (Sn[v] * Tn[u] % MOD)
X = list(it())
total = reduce(lambda a, b: (a + b) % MOD, X, 0)
total = total * total % MOD
sub = reduce(lambda a, b: (a + b) % MOD, map(lambda x: x * x % MOD, X), 0)
print((total - sub) % MOD)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m) = LI()
	(s, t) = LI()
	e = collections.defaultdict(list)
	for _ in range(m):
		(u, v, d) = LI()
		e[u].append((v, d))
		e[v].append((u, d))

	def search(s, t):
		d = collections.defaultdict(lambda : inf)
		dc = collections.defaultdict(int)
		d[s] = 0
		dc[s] = 1
		q = []
		heapq.heappush(q, (0, s))
		v = collections.defaultdict(bool)
		while len(q):
			(k, u) = heapq.heappop(q)
			if v[u]:
				continue
			v[u] = True
			dc[u] %= mod
			if u == t:
				return (d, dc)
			uc = dc[u]
			for (uv, ud) in e[u]:
				if v[uv]:
					continue
				vd = k + ud
				if d[uv] < vd:
					continue
				if d[uv] > vd:
					d[uv] = vd
					dc[uv] = uc
					heapq.heappush(q, (vd, uv))
				elif d[uv] == vd:
					dc[uv] += uc
		return (d, dc)
	(d1, dc1) = search(s, t)
	(d2, dc2) = search(t, s)
	rd = d1[t]
	kk = rd / 2.0
	r = dc1[t] ** 2 % mod
	for k in list(d1.keys()):
		t = d1[k]
		c = dc1[k]
		if t > kk:
			continue
		if t == kk:
			if d2[k] == t:
				r -= pow(c, 2, mod) * pow(dc2[k], 2, mod) % mod
			continue
		for (uv, ud) in e[k]:
			if d2[uv] >= kk or t + ud + d2[uv] != rd:
				continue
			r -= pow(c, 2, mod) * pow(dc2[uv], 2, mod) % mod
	return r % mod
print(main())


import sys
import heapq as hq
mod = 10 ** 9 + 7
readline = sys.stdin.buffer.readline
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))

def dijkstra(G, s, t=None):
	dist = [-1] * len(G)
	fr = [0] * len(G)
	dist[s] = 0
	fr[s] = 1
	q = [(0, s)]
	while q:
		(d, v) = hq.heappop(q)
		if d > dist[v]:
			continue
		for (x, c) in G[v]:
			if dist[x] < 0 or dist[x] > d + c:
				dist[x] = d + c
				fr[x] = fr[v]
				hq.heappush(q, (d + c, x))
			elif dist[x] == d + c:
				fr[x] = (fr[x] + fr[v]) % mod
	return (dist, fr)

def solve():
	(n, m) = nm()
	(s, t) = nm()
	s -= 1
	t -= 1
	G = [list() for _ in range(n)]
	for _ in range(m):
		(u, v, d) = nm()
		u -= 1
		v -= 1
		G[u].append((v, d))
		G[v].append((u, d))
	(diss, frs) = dijkstra(G, s)
	(dist, frt) = dijkstra(G, t)
	cnt = frt[s] * frs[t] % mod
	for i in range(n):
		if diss[i] + dist[i] == dist[s] and diss[i] == dist[i]:
			cnt = (cnt - (frs[i] * frt[i] % mod) ** 2 % mod) % mod
		for (j, x) in G[i]:
			if diss[i] + x + dist[j] == dist[s] and diss[i] < dist[i] and (diss[j] > dist[j]):
				cnt = (cnt - (frs[i] * frt[j] % mod) ** 2 % mod) % mod
	print(cnt)
	return
solve()


from heapq import heappush as k, heappop as l

def f(s):
	a = [1 << 50] * N
	a[s] = 0
	p = [(0, s)]
	while p:
		(d, v) = l(p)
		if d > a[v]:
			continue
		for (u, w) in G[v]:
			if a[u] > d + w:
				a[u] = d + w
				k(p, (d + w, u))
	return a

def g(a, s):
	w = [0] * N
	w[s] = 1
	b = [0] * N
	b[s] = 1
	p = [(0, s)]
	while p:
		(d, v) = l(p)
		for (u, d) in G[v]:
			if a[v] + d == a[u]:
				w[u] = (w[u] + w[v]) % m
				if 1 - b[u]:
					k(p, (a[u], u))
					b[u] = 1
	return w
m = 10 ** 9 + 7
(N, M) = map(int, input().split())
N += 1
(S, T) = map(int, input().split())
G = [[] for _ in [0] * N]
for _ in [0] * M:
	(U, V, D) = map(int, input().split())
	G[U] += [(V, D)]
	G[V] += [(U, D)]
P = f(S)
Q = f(T)
X = g(P, S)
Y = g(Q, T)
s = P[T]
print((X[T] ** 2 - (1 - s % 2) * sum(((X[i] * Y[i]) ** 2 for i in range(N) if P[i] == Q[i] == s // 2)) - sum(((P[i] + d + Q[j] == s) * (P[i] < Q[i]) * (Q[j] < P[j]) * (X[i] * Y[j]) ** 2 for i in range(N) for (j, d) in G[i]))) % m)


from heapq import heappush, heappop
from collections import deque
(N, M) = map(int, input().split())
(S, T) = map(int, input().split())
S -= 1
T -= 1
G = [[] for i in range(N)]
for i in range(M):
	(u, v, d) = map(int, input().split())
	G[u - 1].append((v - 1, d))
	G[v - 1].append((u - 1, d))
INF = 10 ** 18
MOD = 10 ** 9 + 7
dist = [INF] * N
dist[S] = 0
que = [(0, S)]
while que:
	(cost, v) = heappop(que)
	if dist[v] < cost:
		continue
	for (w, c) in G[v]:
		if cost + c < dist[w]:
			dist[w] = cost + c
			heappush(que, (cost + c, w))
que = deque()
mi = [0] * N
que.append(T)
mi[T] = 1
H = [[] for i in range(N)]
RH = [[] for i in range(N)]
D = dist[T]
V = []
E = []
while que:
	v = que.popleft()
	d = dist[v]
	if d * 2 == D:
		V.append(v)
	for (w, c) in G[v]:
		if d == dist[w] + c:
			if dist[w] * 2 < D < d * 2:
				E.append((w, v))
			H[v].append(w)
			RH[w].append(v)
			if mi[w] == 0:
				mi[w] = 1
				que.append(w)

def bfs(G, RG, s):
	(*deg,) = map(len, RG)
	que = deque([s])
	res = [0] * N
	res[s] = 1
	while que:
		v = que.popleft()
		for w in G[v]:
			deg[w] -= 1
			res[w] += res[v]
			if deg[w] == 0:
				que.append(w)
				res[w] %= MOD
	return res
CT = bfs(H, RH, T)
CS = bfs(RH, H, S)
ans = CS[T] * CT[S] % MOD
for v in V:
	ans -= (CS[v] * CT[v]) ** 2
	ans %= MOD
for (v, w) in E:
	ans -= (CS[v] * CT[w]) ** 2
	ans %= MOD
print(ans)


from heapq import heappop, heappush
import sys
(MOD, INF) = (1000000007, float('inf'))

def solve(s, t, links):
	q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
	(visited_fwd, visited_bwd) = ([INF] * n, [INF] * n)
	(patterns_fwd, patterns_bwd) = ([0] * (n + 1), [0] * (n + 1))
	patterns_fwd[-1] = patterns_bwd[-1] = 1
	(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
			patterns_self = patterns_bwd
		else:
			visited_self = visited_fwd
			visited_opp = visited_bwd
			patterns_self = patterns_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
		patterns_self[v] += patterns_self[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:
				patterns_bwd[v] += patterns_bwd[a]
			continue
		if cost_a == collision_time:
			collision_nodes.add(a)
		elif cost == collision_time:
			collision_nodes.add(v)
			patterns_fwd[v] += patterns_fwd[a]
		else:
			collision_links.add((a, v))
	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())
	u -= 1
	v -= 1
	links[u][v] = d
	links[v][u] = d
print(solve(s, t, links))


from heapq import heappop, heappush

def main0(n, m, s, t, abc):
	mod = 10 ** 9 + 7
	g = [set() for _ in range(n)]
	for (i, (a, b, c)) in enumerate(abc):
		(a, b) = (a - 1, b - 1)
		g[a].add((b, c, i))
		g[b].add((a, c, i))
	(s, t) = (s - 1, t - 1)
	todo = [[0, s]]
	inf = float('inf')
	froms = [inf] * n
	froms[s] = 0
	while todo:
		(c, v) = heappop(todo)
		if froms[v] < c:
			continue
		for (nv, nc, _) in g[v]:
			if froms[nv] > c + nc:
				froms[nv] = c + nc
				heappush(todo, [nc + c, nv])
	mincost = froms[t]
	mideary = [0] * m
	midvary = [0] * n
	vary = [0] * n
	vary[t] = 1
	todo = [[0, t]]
	fromt = [inf] * n
	fromt[t] = 0
	fromt[s] = mincost
	while todo:
		(c, v) = heappop(todo)
		for (nv, nc, i) in g[v]:
			if mincost == froms[nv] + c + nc:
				if c < mincost / 2 and c + nc > mincost / 2:
					mideary[i] += vary[v]
					mideary[i] %= mod
				elif mincost % 2 == 0 and c + nc == mincost // 2:
					midvary[nv] += vary[v]
					midvary[nv] %= mod
				vary[nv] += vary[v]
				vary[nv] %= mod
				if fromt[nv] > c + nc:
					fromt[nv] = c + nc
					heappush(todo, [c + nc, nv])
	mideary1 = [0] * m
	midvary1 = [0] * n
	vary = [0] * n
	vary[s] = 1
	todo = [[0, s]]
	nfroms = [inf] * n
	nfroms[s] = 0
	nfroms[t] = mincost
	while todo:
		(c, v) = heappop(todo)
		for (nv, nc, i) in g[v]:
			if mincost == fromt[nv] + c + nc:
				if c < mincost / 2 and c + nc > mincost / 2:
					mideary1[i] += vary[v]
					mideary1[i] %= mod
				elif mincost % 2 == 0 and c + nc == mincost // 2:
					midvary1[nv] += vary[v]
					midvary1[nv] %= mod
				vary[nv] += vary[v]
				vary[nv] %= mod
				if nfroms[nv] > c + nc:
					nfroms[nv] = c + nc
					heappush(todo, [c + nc, nv])
	for i in range(n):
		midvary[i] *= midvary1[i]
		midvary[i] %= mod
	for i in range(m):
		mideary[i] *= mideary1[i]
		mideary[i] %= mod
	summid = sum(mideary) + sum(midvary)
	summid %= mod
	ret = 0
	for x in mideary:
		if x != 0:
			ret += x * (summid - x)
			ret %= mod
	for x in midvary:
		if x != 0:
			ret += x * (summid - x)
			ret %= mod
	return ret
import sys
input = sys.stdin.readline

def __starting_point():
	(n, m) = list(map(int, input().split()))
	(s, t) = list(map(int, input().split()))
	abc = [list(map(int, input().split())) for _ in range(m)]
	print(main0(n, m, s, t, abc))
__starting_point()


def hoge():
	M = 10 ** 9 + 7
	import sys
	input = lambda : sys.stdin.readline().rstrip()
	(n, m) = map(int, input().split())
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	from collections import defaultdict
	ns = defaultdict(set)
	for i in range(m):
		(u, v, d) = map(int, input().split())
		ns[u - 1].add((v - 1, d))
		ns[v - 1].add((u - 1, d))

	def _dijkstra(N, s, Edge):
		import heapq
		geta = 10 ** 15
		inf = geta
		dist = [inf] * N
		dist[s] = 0
		Q = [(0, s)]
		dp = [0] * N
		dp[s] = 1
		while Q:
			(dn, vn) = heapq.heappop(Q)
			if dn > dist[vn]:
				continue
			for (vf, df) in Edge[vn]:
				if dist[vn] + df < dist[vf]:
					dist[vf] = dist[vn] + df
					dp[vf] = dp[vn]
					heapq.heappush(Q, (dn + df, vf))
				elif dist[vn] + df == dist[vf]:
					dp[vf] = (dp[vf] + dp[vn]) % M
		return (dist, dp)

	def dijkstra(start):
		import heapq
		vals = [None] * n
		nums = [None] * n
		nums[start] = 1
		h = [(0, start)]
		vals[start] = 0
		while h:
			(val, u) = heapq.heappop(h)
			for (v, d) in ns[u]:
				if vals[v] is None or vals[v] > val + d:
					vals[v] = val + d
					nums[v] = nums[u]
					heapq.heappush(h, (vals[v], v))
				elif vals[v] is not None and vals[v] == val + d:
					nums[v] = (nums[v] + nums[u]) % M
		return (vals, nums)
	(vals1, nums1) = dijkstra(s)
	(vals2, nums2) = dijkstra(t)
	T = vals1[t]
	c1 = 0
	c2 = 0
	for u in range(n):
		if 2 * vals1[u] == T and 2 * vals2[u] == T:
			c1 = (c1 + pow(nums1[u] * nums2[u], 2, M)) % M
		for (v, d) in ns[u]:
			if vals1[u] + d + vals2[v] == T and 2 * vals1[u] < T < 2 * (vals1[u] + d):
				c2 = (c2 + (nums1[u] * nums2[v]) ** 2) % M
	print((nums1[t] * nums2[s] - (c1 + c2)) % M)
hoge()


from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(G, s):
	INF = 10 ** 18
	dist = [INF] * len(G)
	dist[s] = 0
	pq = [(0, s)]
	while pq:
		(d, v) = heappop(pq)
		if d > dist[v]:
			continue
		for (u, weight) in G[v]:
			nd = d + weight
			if dist[u] > nd:
				dist[u] = nd
				heappush(pq, (nd, u))
	return dist

def count_ways(G, dist, s):
	ways = [0] * len(G)
	ways[s] = 1
	visited = [False] * len(G)
	visited[s] = True
	pq = [(0, s)]
	while pq:
		(d, v) = heappop(pq)
		for (u, d) in G[v]:
			if dist[v] + d == dist[u]:
				ways[u] = (ways[u] + ways[v]) % mod
				if not visited[u]:
					heappush(pq, (dist[u], u))
					visited[u] = True
	return ways
mod = 10 ** 9 + 7
(N, M) = list(map(int, input().split()))
(S, T) = list(map(int, input().split()))
S -= 1
T -= 1
G = [[] for _ in range(N)]
for _ in range(M):
	(U, V, D) = list(map(int, input().split()))
	U -= 1
	V -= 1
	G[U].append((V, D))
	G[V].append((U, D))
distS = dijkstra(G, S)
distT = dijkstra(G, T)
wayS = count_ways(G, distS, S)
wayT = count_ways(G, distT, T)
shortest = distS[T]
cnt = wayS[T] ** 2 % mod
if shortest % 2 == 0:
	for i in range(N):
		if distS[i] == distT[i] == shortest // 2:
			cnt = (cnt - (wayS[i] * wayT[i]) ** 2) % mod
for i in range(N):
	for (j, d) in G[i]:
		if distS[i] + d + distT[j] == shortest:
			if distS[i] < distT[i] and distT[j] < distS[j]:
				cnt = (cnt - (wayS[i] * wayT[j]) ** 2) % mod
print(cnt)


def main():
	from sys import stdin
	input = stdin.readline
	(n, m) = map(int, input().split())
	(s, t) = map(lambda x: int(x) - 1, input().split())
	g = [[] for _ in [0] * n]
	for i in range(m):
		(a, b, c) = map(int, input().split())
		g[a - 1].append((b - 1, c))
		g[b - 1].append((a - 1, c))
	import heapq
	inf = 10 ** 16
	short = inf
	mod = 10 ** 9 + 7
	dist_s = [inf] * n
	dp_s = [0] * n + [1]
	h = [(0, s, -1)]
	heapq.heapify(h)
	while h:
		(d, i, a) = heapq.heappop(h)
		if d > short:
			break
		elif i == t:
			short = d
		d2 = dist_s[i]
		if d2 == inf:
			dist_s[i] = d
			dp_s[i] = dp_s[a]
			for (j, k) in g[i]:
				if dist_s[j] == inf:
					heapq.heappush(h, (d + k, j, i))
		elif d2 == d:
			dp_s[i] = (dp_s[i] + dp_s[a]) % mod
	dist_t = [inf] * n
	dp_t = [0] * n + [1]
	h = [(0, t, -1)]
	heapq.heapify(h)
	while h:
		(d, i, a) = heapq.heappop(h)
		if d > short:
			break
		d2 = dist_t[i]
		if d2 == inf:
			dist_t[i] = d
			dp_t[i] = dp_t[a]
			for (j, k) in g[i]:
				if dist_t[j] == inf:
					heapq.heappush(h, (d + k, j, i))
		elif d2 == d:
			dp_t[i] = (dp_t[i] + dp_t[a]) % mod
	ans = dp_s[t] ** 2 % mod
	for (i, (p, q)) in enumerate(zip(dist_s, dist_t)):
		if p + q == short:
			d = p * 2
			if d == short and q * 2 == short:
				ans = (ans - (dp_s[i] * dp_t[i]) ** 2) % mod
			elif d < short:
				for (j, k) in g[i]:
					if d + 2 * k > short:
						if d + 2 * k + 2 * dist_t[j] == 2 * short:
							ans = (ans - (dp_s[i] * dp_t[j]) ** 2) % mod
	print(ans)
main()


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7

def Dijkstra(adjList, vSt):
	numV = len(adjList)
	numUsed = 0
	costs = [INF] * numV
	costs[vSt] = 0
	nums = [0] * numV
	nums[vSt] = 1
	PQ = []
	heappush(PQ, (0, vSt))
	while PQ:
		(cNow, vNow) = heappop(PQ)
		if cNow > costs[vNow]:
			continue
		numUsed += 1
		if numUsed == numV:
			break
		for (v2, wt) in adjList[vNow]:
			c2 = cNow + wt
			if c2 < costs[v2]:
				costs[v2] = c2
				nums[v2] = nums[vNow]
				heappush(PQ, (c2, v2))
			elif c2 == costs[v2]:
				nums[v2] = (nums[v2] + nums[vNow]) % MOD
	return (costs, nums)

def solve():
	(N, M) = map(int, input().split())
	(S, T) = map(int, input().split())
	(S, T) = (S - 1, T - 1)
	edges = [tuple(map(int, input().split())) for _ in range(M)]
	adjL = [[] for _ in range(N)]
	for (u, v, d) in edges:
		adjL[u - 1].append((v - 1, d))
		adjL[v - 1].append((u - 1, d))
	(costSs, numSs) = Dijkstra(adjL, S)
	(costTs, numTs) = Dijkstra(adjL, T)
	minCost = costSs[T]
	ans = numSs[T] ** 2 % MOD
	for v in range(N):
		if costSs[v] == costTs[v] == minCost / 2:
			k = numSs[v] * numTs[v] % MOD
			ans -= k ** 2 % MOD
			ans %= MOD
	for (u, v, d) in edges:
		(u, v) = (u - 1, v - 1)
		if costSs[u] > costSs[v]:
			(u, v) = (v, u)
		if costSs[u] < minCost / 2 and costTs[v] < minCost / 2 and (costSs[u] + d + costTs[v] == minCost):
			k = numSs[u] * numTs[v] % MOD
			ans -= k ** 2 % MOD
			ans %= MOD
	print(ans)
solve()


import sys
input = sys.stdin.readline
INF = 10 ** 18
mod = 10 ** 9 + 7
import heapq as hp
(N, M) = map(int, input().split())
(s, t) = map(int, input().split())
s -= 1
t -= 1
graph = [[] for _ in range(N)]
for _ in range(M):
	(n, m, d) = map(int, input().split())
	graph[n - 1].append((d, m - 1))
	graph[m - 1].append((d, n - 1))

def dijkstra(s):
	D = [INF for _ in range(N)]
	B = [0] * N
	D[s] = 0
	B[s] = 1
	q = []
	hp.heappush(q, (0, s))
	while q:
		(nd, np) = hp.heappop(q)
		if D[np] < nd:
			continue
		for (d, p) in graph[np]:
			if D[p] > D[np] + d:
				D[p] = D[np] + d
				B[p] = B[np]
				hp.heappush(q, (D[p], p))
			elif D[p] == D[np] + d:
				B[p] = (B[p] + B[np]) % mod
	return (D, B)
(sD, sB) = dijkstra(s)
(tD, tB) = dijkstra(t)
distance = sD[t]
ans = 0
for n in range(N):
	for (d, m) in graph[n]:
		if sD[n] + d + tD[m] == distance and 2 * sD[n] < distance < 2 * (sD[n] + d):
			ans = (ans + (sB[n] * tB[m]) ** 2) % mod
	if sD[n] + tD[n] == distance and 2 * sD[n] == distance:
		ans = (ans + (sB[n] * tB[n]) ** 2) % mod
ans = (sB[t] * tB[s] - ans) % mod
print(ans)


from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
(S, T) = map(int, input().split())
Graph = [set() for i in range(N)]
Edge = []
mod = 10 ** 9 + 7
inf = float('inf')
for i in range(M):
	(a, b, c) = map(int, input().split())
	Graph[a - 1].add((c, b - 1))
	Graph[b - 1].add((c, a - 1))
	Edge.append((a - 1, b - 1, c))
	Edge.append((b - 1, a - 1, c))

def dijkstra(s, n, links):
	Visited = [False] * n
	cost = [inf] * n
	P = [0] * n
	P[s] = 1
	cost[s] = 0
	heap = [(0, s)]
	heapify(heap)
	while heap:
		(hc, hp) = heappop(heap)
		if Visited[hp]:
			continue
		Visited[hp] = True
		for (c, p) in links[hp]:
			if Visited[p]:
				continue
			if c + hc < cost[p]:
				cost[p] = c + hc
				P[p] = P[hp]
				heappush(heap, (cost[p], p))
			elif c + hc == cost[p]:
				P[p] = (P[p] + P[hp]) % mod
	return (cost, P)

def dp(s, n, links, d):
	Visited = [False] * n
	cost = [inf] * n
	P = [0] * n
	P[s] = 1
	cost[s] = 0
	heap = [(0, s)]
	heapify(heap)
	while heap:
		(hc, hp) = heappop(heap)
		if 2 * hc > d:
			break
		if Visited[hp]:
			continue
		Visited[hp] = True
		for (c, p) in links[hp]:
			if Visited[p]:
				continue
			if c + hc < cost[p]:
				cost[p] = c + hc
				P[p] = P[hp]
				heappush(heap, (cost[p], p))
			elif c + hc == cost[p]:
				P[p] = (P[p] + P[hp]) % mod
	return (cost, P)
(cost_S, P_S) = dijkstra(S - 1, N, Graph)
D = cost_S[T - 1]
(cost_T, P_T) = dp(T - 1, N, Graph, D)
Pat = P_S[T - 1]
ans = Pat ** 2 % mod
for (a, b, c) in Edge:
	if cost_S[a] + cost_T[b] + c == D:
		if 2 * cost_S[a] < D and 2 * cost_T[b] < D:
			ans -= (P_S[a] * P_T[b]) ** 2 % mod
for i in range(N):
	if 2 * cost_S[i] == 2 * cost_T[i] == D:
		ans -= (P_S[i] * P_T[i]) ** 2 % mod
print(ans % mod)


from sys import stdin
import heapq

def Dijkstra(lis, start):
	ret = [float('inf')] * len(lis)
	rnum = [0] * len(lis)
	rnum[start] = 1
	ret[start] = 0
	end_flag = [False] * len(lis)
	end_num = 0
	q = [[0, start]]
	while len(q) > 0:
		(ncost, now) = heapq.heappop(q)
		if end_flag[now]:
			continue
		end_flag[now] = True
		end_num += 1
		if end_num == len(lis):
			break
		for (nex, ecost) in lis[now]:
			if ret[nex] > ncost + ecost:
				ret[nex] = ncost + ecost
				heapq.heappush(q, [ret[nex], nex])
				rnum[nex] = 0
			if ret[nex] == ncost + ecost:
				rnum[nex] = (rnum[nex] + rnum[now]) % mod
	return (ret, rnum)
(N, M) = list(map(int, stdin.readline().split()))
(S, T) = list(map(int, stdin.readline().split()))
S -= 1
T -= 1
mod = 10 ** 9 + 7
lis = [[] for i in range(N)]
for i in range(M):
	(u, v, d) = list(map(int, stdin.readline().split()))
	u -= 1
	v -= 1
	lis[u].append((v, d))
	lis[v].append((u, d))
(DS, rootS) = Dijkstra(lis, S)
(DT, rootT) = Dijkstra(lis, T)
ans = rootS[T] ** 2 % mod
L = DS[T]
for v in range(N):
	if L % 2 == 0 and DS[v] == DT[v] == L // 2:
		ans -= (rootS[v] * rootT[v]) ** 2
		continue
	for (nex, ecost) in lis[v]:
		if nex < v:
			if DS[v] + DT[nex] + ecost == L and DS[v] * 2 < L and (DT[nex] * 2 < L):
				ans -= (rootS[v] * rootT[nex]) ** 2
			elif DS[nex] + DT[v] + ecost == L and DS[nex] * 2 < L and (DT[v] * 2 < L):
				ans -= (rootS[nex] * rootT[v]) ** 2
			ans %= mod
print(ans % mod)


def main():
	import sys
	sys.setrecursionlimit(100000)
	input = sys.stdin.readline
	from heapq import heappop, heappush
	mod = 10 ** 9 + 7
	INF = 1 << 60
	(N, M) = list(map(int, input().split()))
	(S, T) = list(map(int, input().split()))
	E = [[] for _ in range(N + 1)]
	edges = []
	for (u, v, d) in zip(*[iter(map(int, sys.stdin.read().split()))] * 3):
		E[u].append((v, d))
		E[v].append((u, d))
		edges.append((u, v, d))

	def dijksrtra(start):
		Dist = [INF] * (N + 1)
		Dist[start] = 0
		q = [0 << 17 | start]
		mask = (1 << 17) - 1
		while q:
			dist_v = heappop(q)
			v = dist_v & mask
			dist = dist_v >> 17
			if Dist[v] != dist:
				continue
			for (u, d) in E[v]:
				new_dist = dist + d
				if Dist[u] > new_dist:
					Dist[u] = new_dist
					heappush(q, new_dist << 17 | u)
		return Dist
	Dist_S = dijksrtra(S)
	Dist_T = dijksrtra(T)
	dist_st = Dist_S[T]
	DAG_edges = []
	DAG = [[] for _ in range(N + 1)]
	DAG_rev = [[] for _ in range(N + 1)]
	for (u, v, d) in edges:
		if Dist_S[u] + Dist_T[v] + d == dist_st:
			DAG_edges.append((u, v))
			DAG[u].append(v)
			DAG_rev[v].append(u)
		elif Dist_T[u] + Dist_S[v] + d == dist_st:
			DAG_edges.append((v, u))
			DAG[v].append(u)
			DAG_rev[u].append(v)
	V = []
	rem = [0] * (N + 1)
	for (_, v) in DAG_edges:
		rem[v] += 1
	q = [S]
	while q:
		v = q.pop()
		V.append(v)
		for u in DAG[v]:
			rem[u] -= 1
			if rem[u] == 0:
				q.append(u)
	n_paths_S = [0] * (N + 1)
	n_paths_T = [0] * (N + 1)
	n_paths_S[S] = 1
	n_paths_T[T] = 1
	for v in V:
		n = n_paths_S[v]
		for u in DAG[v]:
			n_paths_S[u] += n
	for v in V[::-1]:
		n = n_paths_T[v]
		for u in DAG_rev[v]:
			n_paths_T[u] += n
	ans = n_paths_S[T]
	ans = ans * ans % mod
	for (v, u) in DAG_edges:
		if Dist_S[v] * 2 < dist_st and dist_st < Dist_S[u] * 2:
			ans = (ans - (n_paths_S[v] * n_paths_T[u]) ** 2) % mod
	for (v, (dist, ns, nt)) in enumerate(zip(Dist_S, n_paths_S, n_paths_T)):
		if dist * 2 == dist_st:
			ans = (ans - (ns * nt) ** 2) % mod
	print(ans)
main()


import sys
from collections import deque, defaultdict
import heapq
input = sys.stdin.buffer.readline

def dijkstra(adj, start):
	dist = [float('inf')] * len(adj)
	dist[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(min_dist, v_from) = heapq.heappop(q)
		if min_dist > dist[v_from]:
			continue
		v_tos = adj[v_from]
		for (v_to, cost) in v_tos:
			if min_dist + cost < dist[v_to]:
				dist[v_to] = min_dist + cost
				heapq.heappush(q, (dist[v_to], v_to))
	return dist

def main():
	mod = 10 ** 9 + 7
	(N, M) = map(int, input().split())
	(s, t) = map(int, input().split())
	adj = [[] for _ in range(N + 1)]
	for _ in range(M):
		(l, r, d) = map(int, input().split())
		adj[l].append((r, d))
		adj[r].append((l, d))
	dist = dijkstra(adj, s)
	collision_T = dist[t] / 2 if dist[t] % 2 == 1 else dist[t] // 2
	route = [0] * (N + 1)
	route[t] = 1
	que = []
	heapq.heappush(que, (-dist[t], t))
	col_edge = set()
	seen = [0] * (N + 1)
	seen[t] = 1
	while que:
		(_, v) = heapq.heappop(que)
		for (u, d) in adj[v]:
			if dist[v] == dist[u] + d:
				route[u] = (route[u] + route[v]) % mod
				if dist[u] < collision_T < dist[v]:
					col_edge.add((u, v))
				elif dist[v] == collision_T:
					col_edge.add((v, v))
				if not seen[u]:
					heapq.heappush(que, (-dist[u], u))
					seen[u] = 1
	route2 = [0] * (N + 1)
	route2[s] = 1
	que = []
	heapq.heappush(que, (0, s))
	seen = [0] * (N + 1)
	seen[s] = 1
	while que:
		(_, v) = heapq.heappop(que)
		for (u, d) in adj[v]:
			if dist[u] == dist[v] + d:
				route2[u] = (route2[u] + route2[v]) % mod
				if not seen[u]:
					heapq.heappush(que, (dist[u], u))
					seen[u] = 1
	ans = pow(route[s], 2, mod)
	for (u, v) in col_edge:
		tmp = route[v] * route2[u] % mod
		ans = (ans - pow(tmp, 2, mod)) % mod
	print(ans)
main()


import heapq
import sys
input = sys.stdin.buffer.readline

def dijkstra(start: int, graph: list) -> list:
	INF = 10 ** 18
	MOD = 10 ** 9 + 7
	n = len(graph)
	dist = [INF] * n
	ptn = [0] * n
	dist[start] = 0
	ptn[start] = 1
	q = [(0, start)]
	while q:
		(d, v) = heapq.heappop(q)
		if dist[v] < d:
			continue
		for (nxt_v, cost) in graph[v]:
			if dist[v] + cost == dist[nxt_v]:
				ptn[nxt_v] += ptn[v]
				ptn[nxt_v] %= MOD
			if dist[v] + cost < dist[nxt_v]:
				dist[nxt_v] = dist[v] + cost
				ptn[nxt_v] = ptn[v]
				ptn[nxt_v] %= MOD
				heapq.heappush(q, (dist[nxt_v], nxt_v))
	return (dist, ptn)
(n, m) = list(map(int, input().split()))
(s, t) = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
MOD = 10 ** 9 + 7
s -= 1
t -= 1
graph = [[] for i in range(n)]
for (a, b, cost) in info:
	a -= 1
	b -= 1
	graph[a].append((b, cost))
	graph[b].append((a, cost))
(dist_st, ptn_st) = dijkstra(s, graph)
(dist_ts, ptn_ts) = dijkstra(t, graph)
(min_cost, max_ptn) = (dist_st[t], ptn_st[t])
all_ptn = max_ptn * max_ptn % MOD
use = [False] * n
use[t] = True
stack = [t]
while stack:
	v = stack.pop()
	for (prv_v, cost) in graph[v]:
		if use[prv_v]:
			continue
		if dist_st[v] == dist_st[prv_v] + cost:
			use[prv_v] = True
			stack.append(prv_v)
for i in range(n):
	if dist_st[i] == dist_ts[i] and use[i]:
		all_ptn -= (ptn_st[i] * ptn_ts[i]) ** 2
		all_ptn %= MOD
for (a, b, cost) in info:
	a -= 1
	b -= 1
	if abs(dist_st[a] - dist_st[b]) != cost:
		continue
	if not use[a] or not use[b]:
		continue
	if dist_st[a] > dist_st[b]:
		(a, b) = (b, a)
	if dist_st[a] < dist_ts[a] and dist_st[b] > dist_ts[b]:
		all_ptn -= (ptn_st[a] * ptn_ts[b]) ** 2
	all_ptn %= MOD
print(all_ptn)


from heapq import *

def dijkstra(g, start):
	n = len(g)
	INF = 1 << 61
	dist = [INF] * n
	num = [0] * n
	dist[start] = 0
	num[start] = 1
	q = [(0, start)]
	while q:
		(dv, v) = heappop(q)
		if dist[v] < dv:
			continue
		for (to, cost) in g[v]:
			if dv + cost < dist[to]:
				dist[to] = dv + cost
				num[to] = num[v]
				heappush(q, (dist[to], to))
			elif dv + cost == dist[to]:
				num[to] += num[v]
				num[to] %= MOD
	return (dist, num)
import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, m) = list(map(int, readline().split()))
(s, t) = list(map(int, readline().split()))
s -= 1
t -= 1
g = [[] for _ in range(n)]
edges = []
for _ in range(m):
	(a, b, c) = list(map(int, readline().split()))
	g[a - 1].append((b - 1, c))
	g[b - 1].append((a - 1, c))
	edges.append((a - 1, b - 1, c))
MOD = 10 ** 9 + 7
(dist, num) = dijkstra(g, s)
(dt, nt) = dijkstra(g, t)
ans = num[t] ** 2
D = dist[t]
for i in range(n):
	if dist[i] * 2 == D and dist[i] + dt[i] == dist[t]:
		ans -= (num[i] * nt[i] % MOD) ** 2 % MOD
for (a, b, c) in edges:
	da = dist[a]
	db = dist[b]
	if da > db:
		(a, b) = (b, a)
		(da, db) = (db, da)
	if da * 2 < D and db * 2 > D and (dist[a] + dt[b] + c == dist[t]):
		ans -= (num[a] * nt[b] % MOD) ** 2 % MOD
print(ans % MOD)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

def dijkstra(s):
	hq = [(0, s)]
	dist = [INF] * n
	dp = [0] * n
	dp[s] = 1
	dist[s] = 0
	checked = [0] * n
	while hq:
		(min_dist, u) = heappop(hq)
		if checked[u]:
			continue
		checked[u] = 1
		for (v, c) in G[u]:
			if dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				dp[v] = dp[u]
				heappush(hq, (dist[v], v))
			elif dist[u] + c == dist[v]:
				dp[v] += dp[u]
				dp[v] %= mod
	return (dp, dist)
(n, m) = LI()
(s, t) = LI()
G = [[] for _ in range(n)]
for _ in range(m):
	(a, b, d) = LI()
	G[a - 1] += [(b - 1, d)]
	G[b - 1] += [(a - 1, d)]
(dp1, dist1) = dijkstra(s - 1)
(dp2, dist2) = dijkstra(t - 1)
total = dist1[t - 1]
ans = dp1[t - 1] * dp2[s - 1] % mod
for i in range(n):
	if dist1[i] == dist2[i] == total / 2:
		ans -= pow(dp1[i] * dp2[i] % mod, 2, mod)
for j in range(n):
	for (k, ci) in G[j]:
		if dist1[j] + dist2[k] + ci == total and dist1[j] < total / 2 and (dist2[k] < total / 2):
			ans -= pow(dp1[j] * dp2[k] % mod, 2, mod)
print(ans % mod)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
(S, T) = map(int, input().split())
mod = 10 ** 9 + 7
e = [[] for _ in range(N + 1)]
for _ in range(M):
	(u, v, c) = map(int, input().split())
	e[u].append((v, c))
	e[v].append((u, c))
import heapq
hpush = heapq.heappush
hpop = heapq.heappop

class dijkstra:

	def __init__(self, n, e):
		self.e = e
		self.n = n

	def path(self, s):
		d = [float('inf')] * (self.n + 1)
		vis = [0] * (self.n + 1)
		d[s] = 0
		h = [s]
		while len(h):
			v = hpop(h)
			v1 = v % 10 ** 6
			v0 = v // 10 ** 6
			if vis[v1]:
				continue
			vis[v1] = 1
			for p in self.e[v1]:
				d[p[0]] = min(d[p[0]], d[v1] + p[1])
				if vis[p[0]]:
					continue
				hpush(h, d[p[0]] * 10 ** 6 + p[0])
		return d
dij = dijkstra(N, e)
ps = dij.path(S)
pt = dij.path(T)
dps = [0] * (N + 1)
dpt = [0] * (N + 1)
dps[S] = 1
h = []
for x in range(1, N + 1):
	hpush(h, (ps[x], x))
while len(h):
	(_, x) = hpop(h)
	for (y, c) in e[x]:
		if ps[y] > ps[x] and ps[y] - ps[x] == c:
			dps[y] += dps[x]
			dps[y] %= mod
dpt[T] = 1
h = []
for x in range(1, N + 1):
	hpush(h, (pt[x], x))
while len(h):
	(_, x) = hpop(h)
	for (y, c) in e[x]:
		if pt[y] > pt[x] and pt[y] - pt[x] == c:
			dpt[y] += dpt[x]
			dpt[y] %= mod
res = dps[T] * dpt[S] % mod
for x in range(1, N + 1):
	if ps[x] == pt[x]:
		if ps[x] + pt[x] > ps[T]:
			continue
		res -= dps[x] ** 2 * dpt[x] ** 2 % mod
		res %= mod
for x in range(1, N + 1):
	for (y, c) in e[x]:
		if ps[y] - ps[x] == c and ps[y] * 2 > ps[T] and (ps[x] * 2 < ps[T]):
			if ps[x] + pt[y] + c > ps[T]:
				continue
			res -= dps[x] ** 2 * dpt[y] ** 2 % mod
			res %= mod
print(res)


import heapq
import sys

def input():
	return sys.stdin.readline()[:-1]
MOD = 10 ** 9 + 7

class DijkstraList:

	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [float('inf') for _ in range(self.size)]
		self.dist[self.start] = 0
		self.dp = [0 for _ in range(self.size)]
		self.dp[self.start] = 1
		self.q = []
		self.cnt = 0
		heapq.heappush(self.q, (0, self.start))
		while self.q and self.cnt < self.size:
			(u_dist, u) = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for (v, w) in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.dp[v] = self.dp[u]
					heapq.heappush(self.q, (self.dist[v], v))
				elif self.dist[v] == u_dist + w:
					self.dp[v] += self.dp[u]
					self.dp[v] %= MOD
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

	def get_dp(self, x):
		return self.dp[x]
(n, m) = map(int, input().split())
(s, t) = map(int, input().split())
(s, t) = (s - 1, t - 1)
adj = [[] for _ in range(n)]
for _ in range(m):
	(u, v, d) = map(int, input().split())
	adj[u - 1].append([v - 1, d])
	adj[v - 1].append([u - 1, d])
(S, T) = (DijkstraList(adj, s), DijkstraList(adj, t))
S.solve()
T.solve()
ans = pow(S.get_dp(t), 2, MOD)
goal = S.distance(t)
for i in range(n):
	(SI, TI) = (S.distance(i), T.distance(i))
	if SI + TI != goal:
		continue
	if SI * 2 == goal:
		ans -= S.get_dp(i) * T.get_dp(i) * S.get_dp(i) * T.get_dp(i)
		ans %= MOD
	else:
		for (j, d) in adj[i]:
			if i > j:
				continue
			(SJ, TJ) = (S.distance(j), T.distance(j))
			if SJ + TJ != goal or abs(SI - SJ) != d:
				continue
			if SI * 2 < goal < SJ * 2:
				ans -= S.get_dp(i) * T.get_dp(j) * S.get_dp(i) * T.get_dp(j)
				ans %= MOD
			elif SJ * 2 < goal < SI * 2:
				ans -= S.get_dp(j) * T.get_dp(i) * S.get_dp(j) * T.get_dp(i)
				ans %= MOD
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from heapq import *
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
(S, T) = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
	(u, v, d) = map(int, input().split())
	graph[u].append((v, d))
	graph[v].append((u, d))

def dijkstra(S):
	INF = 10 ** 15
	dist = [INF] * (N + 1)
	cnt_path = [0] * (N + 1)
	cnt_path[S] = 1
	q = [(0, S)]
	while q:
		(d, x) = heappop(q)
		if dist[x] < d:
			continue
		dist[x] = d
		for (y, dy) in graph[x]:
			if d + dy > dist[y]:
				continue
			if d + dy == dist[y]:
				cnt_path[y] += cnt_path[x]
				continue
			cnt_path[y] = cnt_path[x]
			dist[y] = d + dy
			heappush(q, (d + dy, y))
	return (dist, cnt_path)
(dist_S, cnt_path_S) = dijkstra(S)
(dist_T, cnt_path_T) = dijkstra(T)
D = dist_S[T]
answer = cnt_path_S[T] * cnt_path_T[S]
for x in range(1, N + 1):
	if dist_S[x] == dist_T[x]:
		t = cnt_path_S[x] * cnt_path_T[x] % MOD
		answer -= t * t % MOD
for x in range(1, N + 1):
	for (y, d) in graph[x]:
		dx = dist_S[x]
		dy = dist_T[y]
		if dx + dy + d == D and dx + d > dy and (dy + d > dx):
			t = cnt_path_S[x] * cnt_path_T[y] % MOD
			answer -= t * t % MOD
answer %= MOD
print(answer)


mod = 10 ** 9 + 7

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def edge(self, _from):
		return self.G[_from]

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		cnt = [0] * self.V
		cnt[s] = 1
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
					cnt[e.to] = cnt[v] % mod
				elif d[e.to] == d[v] + e.cost:
					cnt[e.to] += cnt[v]
					cnt[e.to] %= mod
		return (d, cnt)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
(N, M) = list(map(int, input().split()))
(S, T) = list(map(int, input().split()))
mati = Dijkstra(N)
for i in range(M):
	(u, v, d) = list(map(int, input().split()))
	mati.add(u - 1, v - 1, d)
	mati.add(v - 1, u - 1, d)
(spath, Sways) = mati.shortest_path(S - 1)
(tpath, Tways) = mati.shortest_path(T - 1)
ans = Sways[T - 1] * Tways[S - 1]
ans %= mod
for u in range(N):
	for e in mati.edge(u):
		v = e.to
		d = e.cost
		ans -= (Tways[v] * Sways[u]) ** 2 * (spath[u] + d + tpath[v] == spath[T - 1] and spath[u] + d != tpath[v] and (spath[u] != tpath[v] + d) and (tpath[v] + d >= spath[u] >= tpath[v] or tpath[v] + d >= spath[u] + d >= tpath[v]))
		ans %= mod
for i in range(N):
	ans -= (Tways[i] * Sways[i]) ** 2 * (spath[i] + tpath[i] == spath[T - 1] and spath[i] == tpath[i])
	ans %= mod
print(ans % mod)


from heapq import heapify, heappush, heappop

def conv(c, p, pp):
	return (c * N + p) * N + pp

def rev(X):
	pp = X % N
	X //= N
	p = X % N
	c = X // N
	return (c, p, pp)
MOD = 10 ** 9 + 7
(N, M) = list(map(int, input().split()))
(s, t) = list(map(int, input().split()))
s -= 1
t -= 1
I = [[] for _ in range(N)]
edges = []
for _ in range(M):
	(u, v, c) = list(map(int, input().split()))
	u -= 1
	v -= 1
	I[u].append((v, c))
	I[v].append((u, c))
	edges.append(conv(c, u, v))
fin_i = [0 for _ in range(N)]
ml_i = [0 for _ in range(N)]
fin_r = [0 for _ in range(N)]
ml_r = [0 for _ in range(N)]

def dijkstra(s, fin, ml):
	task = [conv(0, s, s)]
	fin[s] = 1
	ml[s] = 0
	vis = set()
	while task:
		while True:
			if not task:
				return
			(c, p, pp) = rev(heappop(task))
			if p in vis and c == ml[p]:
				fin[p] += fin[pp]
				fin[p] %= MOD
			elif p not in vis:
				break
		if p != s:
			fin[p] += fin[pp]
			fin[p] %= MOD
			ml[p] = c
		vis.add(p)
		for (q, c_n) in I[p]:
			if q not in vis:
				heappush(task, conv(c + c_n, q, p))
	return
dijkstra(s, fin_i, ml_i)
dijkstra(t, fin_r, ml_r)
L = ml_i[t]
ans = 0
for X in edges:
	(c, u, v) = rev(X)
	if ml_i[u] + c + ml_r[v] == L and ml_i[u] * 2 < L < ml_i[v] * 2:
		ans += (fin_i[u] * fin_r[v]) ** 2
	(u, v) = (v, u)
	if ml_i[u] + c + ml_r[v] == L and ml_i[u] * 2 < L < ml_i[v] * 2:
		ans += (fin_i[u] * fin_r[v]) ** 2
		ans %= MOD
for p in range(N):
	if 2 * ml_i[p] == L:
		ans += (fin_i[p] * fin_r[p]) ** 2
		ans %= MOD
print((fin_i[t] ** 2 - ans) % MOD)


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)
		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()


from heapq import *

def f(s):
	a = [1 << 50] * N
	a[s] = 0
	p = [(0, s)]
	c = [0] * N
	c[s] = 1
	while p:
		(d, v) = heappop(p)
		if d <= a[v]:
			for (u, w) in G[v]:
				if a[u] > d + w:
					a[u] = d + w
					heappush(p, (d + w, u))
					c[u] = 0
				c[u] += c[v] * (a[u] == d + w)
	return (a, c)
n = lambda : map(int, input().split())
(N, M) = n()
N += 1
(S, T) = n()
G = [[] for _ in [0] * N]
for _ in [0] * M:
	(U, V, D) = n()
	G[U] += ((V, D),)
	G[V] += ((U, D),)
(P, X) = f(S)
(Q, Y) = f(T)
s = P[T]
print((X[T] ** 2 - sum((-~s % 2 * x * x * y * y * (p == q == s // 2) + (p < q) * x * x * sum(((p + d + Q[j] == s) * (Q[j] < P[j]) * Y[j] ** 2 for (j, d) in g)) for (g, p, q, x, y) in zip(G, P, Q, X, Y)))) % (10 ** 9 + 7))


from collections import defaultdict, deque
from heapq import heappop, heappush

def inpl():
	return list(map(int, input().split()))
(N, M) = inpl()
(S, T) = inpl()
G = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7
for _ in range(M):
	(u, v, d) = inpl()
	G[u].append((v, d))
	G[v].append((u, d))
cost = [10 ** 18] * (N + 1)
appear = [0] * (N + 1)
Q = [(0, S)]
cost[S] = 0
appear[S] = 1
while Q:
	(c, p) = heappop(Q)
	if cost[p] < c:
		continue
	for (q, d) in G[p]:
		if cost[p] + d == cost[q]:
			appear[q] = (appear[q] + appear[p]) % MOD
		elif cost[p] + d < cost[q]:
			cost[q] = cost[p] + d
			appear[q] = appear[p] % MOD
			heappush(Q, (cost[q], q))
end = cost[T] * 1
ans = pow(appear[T], 2, MOD)
Q = [(0, T)]
cost2 = [10 ** 18] * (N + 1)
cost2[T] = 0
appear2 = [0] * (N + 1)
appear2[T] = 1
while Q:
	(c, p) = heappop(Q)
	if cost2[p] < c:
		continue
	for (q, d) in G[p]:
		if cost[p] - d != cost[q]:
			continue
		if cost2[p] + d == cost2[q]:
			appear2[q] = (appear2[q] + appear2[p]) % MOD
		elif cost2[p] + d < cost2[q]:
			cost2[q] = cost2[p] + d
			appear2[q] = appear2[p] % MOD
			heappush(Q, (cost2[q], q))
Q = deque([S])
searched = [False] * (N + 1)
searched[S] = True
while Q:
	p = Q.pop()
	if 2 * cost2[p] == end:
		ans = (ans - (appear[p] * appear2[p]) ** 2) % MOD
	for (q, d) in G[p]:
		if cost2[p] - d != cost2[q]:
			continue
		if 2 * cost2[q] < end < 2 * cost2[p]:
			ans = (ans - (appear[p] * appear2[q]) ** 2) % MOD
		if not searched[q]:
			Q.append(q)
			searched[q] = True
print(ans)