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: competition

Starter code:

Solutions:
# ARC090E

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

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


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])**2for 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])**2for i in range(N)for j,d in G[i]))%m)

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)

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
  #print(mincost,mideary,midvary)
  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()

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)

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)]
#S,Tからdijkstra
#distX[i]: [Xからiへの最短経路長、そのパスの本数]
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]
#dst: S-T間の距離
#anslsに「2人が出会いうる辺/頂点を通るパスの本数」を格納
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
#答え: anslsの要素をaiとすると
#(Σai)^2-Σ(ai^2)になるはず…

print(ans%mod)

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 list(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 list(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 = list(map(int, input().split()))
s, t = list(map(int, input().split()))
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = list(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)))


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--~s%2*sum((x*y)**2for x,y,p,q in zip(X,Y,P,Q)if p==q==s//2)-sum((P[i]+d+Q[j]==s)*(P[i]<Q[i])*(Q[j]<P[j])*(X[i]*Y[j])**2for 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 heapq
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 10**9+7
class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	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.prev = [-1 for _ in range(self.size)]
		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]
					#self.prev[v] = 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
		#print(self.dp)
		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)
#print(ans, goal)

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:
				#print(i, j, SI, SJ)
				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:
				#print(i, j, SI, SJ)
				ans -= S.get_dp(j) * T.get_dp(i) * S.get_dp(j) * T.get_dp(i)
				ans %= MOD

print(ans)

mod=10**9+7

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        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):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

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

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        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)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
                    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 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)

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 _ in range(M):
    #     u, v, d = map(int, input().split())
    #     E[u].append((v, d))
    #     E[v].append((u, d))
    #     edges.append((u, v, d))
    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 = []  # S -> T
    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 = [-1] * (N+1)
    # n_paths_T = [-1] * (N+1)
    n_paths_S = [0] * (N+1)
    n_paths_T = [0] * (N+1)
    n_paths_S[S] = 1
    n_paths_T[T] = 1
    # def calc_n_paths_S(v):
    #     if n_paths_S[v] != -1:
    #         return n_paths_S[v]
    #     res = 0
    #     for u in DAG_rev[v]:
    #         res = (res + calc_n_paths_S(u)) % mod
    #     n_paths_S[v] = res
    #     return res
    # def calc_n_paths_T(v):
    #     if n_paths_T[v] != -1:
    #         return n_paths_T[v]
    #     res = 0
    #     for u in DAG[v]:
    #         res = (res + calc_n_paths_T(u)) % mod
    #     n_paths_T[v] = res
    #     return res

    # ans = calc_n_paths_S(T)  # 全経路数
    # calc_n_paths_T(S)

    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
input = sys.stdin.readline

INF = 10**18
mod = 10**9+7
# AOJ GRL_1_A Single Sourse Shortest Path
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)] # 頂点iへの最短距離がD[i]
    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)

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)

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--~s%2*sum((x*y)**2for x,y,p,q in zip(X,Y,P,Q)if p==q==s//2)-sum((P[i]+d+Q[j]==s)*(P[i]<Q[i])*(Q[j]<P[j])*(X[i]*Y[j])**2for i in range(N)for j,d in G[i]))%(10**9+7))

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]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
sm = sum(ansls)%mod
ans = sm**2%mod
for i in ansls:
  ans = (ans-i**2)%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*
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]**2for j,d in g)for g,p,q,x,y in zip(G,P,Q,X,Y)))%(10**9+7))

import heapq
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 10**9+7
class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	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.prev = [-1 for _ in range(self.size)]
		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]
					#self.prev[v] = 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
		#print(self.dp)
		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)
#print(ans, goal)

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:
				#print(i, j, SI, SJ)
				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:
				#print(i, j, SI, SJ)
				ans -= S.get_dp(j) * T.get_dp(i) * S.get_dp(j) * T.get_dp(i)
				ans %= MOD

print(ans)

import sys
def MI(): return list(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]  # Sから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)


from heapq import heappush,heappop
def f(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 g(a,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 a[v]+d==a[u]:
                w[u]=(w[u]+w[v])%m
                if not b[u]:heappush(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)]
dS=f(S)
dT=f(T)
wS=g(dS,S)
wT=g(dT,T)
s=dS[T]
a=(wS[T]**2-(1-s%2)*sum((wS[i]*wT[i])**2for i in range(N)if dS[i]==dT[i]==s//2))%m
for i in range(N):
    for j,d in G[i]:
        if(dS[i]+d+dT[j]==s)*(dS[i]<dT[i])*(dT[j]<dS[j]):a=(a-(wS[i]*wT[j])**2)%m
print(a)


"""

両方から距離Lの点の数がわかればよい
STからダイクストラ

頂点がなる場合→調べる
辺の間でなる場合
両方近いほうが異なる & その和+辺の長さが2L

ぶつかるものを引きたい
その頂点までの経路数も求めておく

"""

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
        #print (now,rnum)
    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]

#print (DS,rootS)

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():
    from sys import stdin
    input = stdin.readline

    n, m = list(map(int, input().split()))
    s, t = [int(x)-1 for x in input().split()]
    g = [[] for _ in [0]*n]
    for i in range(m):
        a, b, c = list(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 = 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))







from heapq import heappush,heappop
def f(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 g(a,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 a[v]+d==a[u]:
                w[u]=(w[u]+w[v])%m
                if not b[u]:heappush(p,(a[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=f(S)
dT=f(T)
wS=g(dS,S)
wT=g(dT,T)
s=dS[T]
a=(wS[T]**2-(1-s%2)*sum((wS[i]*wT[i])**2for i in range(N)if dS[i]==dT[i]==s//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])*(dT[j]<dS[j]):a=(a-(wS[i]*wT[j])**2)%m
print(a)

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
      #print(task)
      c, p, pp = rev(heappop(task))
      #print(c, p, pp, task)
      if p in vis and c == ml[p]:
        #print(p, pp, 1, vis)
        fin[p] += fin[pp]
        fin[p] %= MOD
      elif p not in vis:
        #print(p)
        break
    if p != s:
      #print(p, pp, 2)
      fin[p] += fin[pp]
      fin[p] %= MOD
      ml[p] = c
    vis.add(p)
    #print(p, I[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)
#print(ml_i)
#print(fin_i)
#print(ml_r)
#print(fin_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:
    #print(u, v, fin_i[u], fin_r[v])
    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:
    #print(u, v, fin_i[u], fin_r[v])
    ans += (fin_i[u] * fin_r[v]) ** 2
    ans %= MOD
for p in range(N):
  if 2*ml_i[p] == L:
    #print(p, fin_i[p] * fin_r[p])
    ans += (fin_i[p] * fin_r[p]) ** 2
    ans %= MOD
    
print(((fin_i[t]**2 - ans) %MOD))


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 list(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 = list(map(int, input().split()))
s, t = list(map(int, input().split()))
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = list(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)))


from heapq import heappush, heappop
from collections import deque
N, M = list(map(int, input().split()))
S, T = list(map(int, input().split()))
S -= 1; T -= 1
G = [[] for i in range(N)]
for i in range(M):
    u, v, d = list(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, = list(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 *
def dijkstra(g,start):
    n = len(g)
    INF = 1<<61
    dist = [INF]*(n) #startからの最短距離
    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

# coding: utf-8
# Your code here!
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)

#print(dist,dt)
#print(num,nt)

ans = num[t]**2
#print(ans,"original")

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

#print(ans,"remove-pt")

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


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

            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 -= (c**2 * dc2[k]**2) % mod
            continue

        for uv, ud in e[k]:
            if d2[uv] >= kk or t + ud + d2[uv] != rd:
                continue
            r -= (c**2 * dc2[uv]**2) % mod

    return r % mod




print(main())


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--~s%2*sum(x*x*y*y*(p==q==s//2)for x,y,p,q in zip(X,Y,P,Q))-sum((P[i]+d+Q[j]==s)*(P[i]<Q[i])*(Q[j]<P[j])*(X[i]*Y[j])**2for i in range(N)for j,d in G[i]))%(10**9+7))

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])**2for 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])**2for i in range(N)for j,d in G[i]))%(10**9+7))

from heapq import heappush as k,heappop as l
def f(s):
    a=[1<<50]*N;a[s]=0;p=[(0,s)]
    c=[0]*N;c[s]=1
    while p:
        d,v=l(p)
        if d>a[v]:continue
        for u,w in G[v]:
            if a[u]==d+w:
                c[u]+=c[v]
            if a[u]>d+w:
                a[u]=d+w;k(p,(d+w,u))
                c[u]=c[v]
    return a,c
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,X=f(S);Q,Y=f(T);s=P[T]
print((X[T]**2-(1-s%2)*sum((X[i]*Y[i])**2for 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])**2for i in range(N)for j,d in G[i]))%m)

import heapq
MOD = 10 ** 9 + 7

N, M = list(map(int, input().split()))
S, T = [int(x) - 1 for x in input().split()]

adjList = [[] for i in range(N)]
for i in range(M):
    U, V, D = list(map(int, input().split()))
    adjList[U - 1].append((V - 1, D))
    adjList[V - 1].append((U - 1, D))

# 頂点Sから各頂点への最短路の個数
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))

# 頂点Tから各頂点への最短路の個数
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)


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


from heapq import heappop, heappush
MOD = 10 ** 9 + 7

N, M = list(map(int, input().split()))
S, T = [int(x) - 1 for x in input().split()]

adjList = [[] for i in range(N)]
for i in range(M):
    U, V, D = list(map(int, input().split()))
    adjList[U - 1].append((V - 1, D))
    adjList[V - 1].append((U - 1, D))

# 頂点Sから各頂点への最短路の個数
numRouteS = [0] * N
numRouteS[S] = 1

cost = [float('inf')] * N
cost[S] = 0
prev = [None] * N
vs = []

pq = []
heappush(pq, (0, S))
while pq:
    c, vNow = heappop(pq)
    if c > cost[vNow]: continue
    if c > cost[T]: break
    vs += [vNow]

    for v2, wt in adjList[vNow]:
        c2 = c + wt
        if c2 < cost[v2]:
            cost[v2] = c2
            prev[v2] = [vNow]
            numRouteS[v2] = numRouteS[vNow]
            heappush(pq, (c2, v2))
        elif c2 == cost[v2]:
            prev[v2] += [vNow]
            numRouteS[v2] = (numRouteS[v2] + numRouteS[vNow]) % MOD

# 頂点Tから各頂点への最短路の個数
numRouteT = [0] * N
numRouteT[T] = 1
cST = cost[T]
for iV, v in enumerate(reversed(vs)):
    if cost[v] * 2 < cST:
        iVLim = len(vs) - iV
        break
    for v0 in prev[v]:
        numRouteT[v0] = (numRouteT[v0] + numRouteT[v]) % MOD

# 二人の最短路の選び方の組から、途中で出会うものを引く
ans = (numRouteS[T] ** 2) % MOD

for v in vs[:iVLim]:
    x = (numRouteS[v] ** 2) % MOD
    for v2, wt in adjList[v]:
        if (cost[v2] * 2 > cST) and cost[v] + wt == cost[v2]:
            y = (numRouteT[v2] ** 2) % MOD
            ans = (ans - x * y) % MOD

for v in vs[iVLim:]:
    if cost[v] * 2 > cST: break
    x = (numRouteS[v] ** 2) % MOD
    y = (numRouteT[v] ** 2) % MOD
    ans = (ans - x * y) % MOD

print(ans)


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
    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--~s%2*sum((X[i]*Y[i])**2for 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])**2for i in range(N)for j,d in G[i]))%(10**9+7))

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 = list(map(int, input().split()))
    S, T = list(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()


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)


from heapq import heapify,heappop,heappush
import sys
input=sys.stdin.readline
N,M=list(map(int,input().split()))
S,T=list(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=list(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 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))