CodeEff/ECCO huggingface dataset:
# Original solution
N = int(eval(input()))
x = [list(map(int, input().split())) for i in range(N)]
cnt = 0
sum = 0
flag = 0
T = X = Y = 0
for i in range(N):
    cnt = x[i][0] - T
    sum = abs(x[i][1]- X) + abs(x[i][2]- Y)
    T = x[i][0]
    X = x[i][1]
    Y = x[i][2]
    if cnt < sum or cnt % 2 != sum % 2:
        flag = 1
        break
if flag == 0:
    print("Yes")
else:
    print("No")


# Optimized solution
N = int(eval(input()))
x = [list(map(int, input().split())) for i in range(N)]
cnt = 0
sum = 0
flag = 0
for i in range(N):
    if i == 0:
        cnt = x[i][0]
        sum = x[i][1] + x[i][2]
    else:
        cnt = x[i][0] - x[i-1][0]
        sum = abs(x[i][1]-x[i-1][1]) + abs(x[i][2]-x[i-1][2])
    if cnt < sum or cnt % 2 != sum % 2:
        flag = 1
        break
if flag == 0:
    print("Yes")
else:
    print("No")
# Original solution
# -*- coding: utf-8 -*-

option = {(0, 0)}


def main():
    global option
    last_list = [0, 0, 0]
    N = int(eval(input()))
    for i in range(N):
        this_list = list(map(int, input().split()))
        add_option(this_list[0] - last_list[0], (this_list[1], this_list[2]))
        if (this_list[1], this_list[2]) not in option:
            print('No')
            return
        option = {(this_list[1], this_list[2])}
        last_list = this_list
    print('Yes')


def add_option(step, this_postion):
    global option
    xi, yi = this_postion
    for i in range(step):
        temp_option = set()
        rest = step - i
        for position in option:
            x, y = position
            diff = abs(x - xi) + abs(y - yi)
            if rest % 2 != diff % 2:
                continue
            if diff > rest:
                continue
            if x < 100000:
                temp_option.add((x + 1, y))
            if y < 100000:
                temp_option.add((x, y + 1))
            if x > 0:
                temp_option.add((x - 1, y))
            if y > 0:
                temp_option.add((x, y - 1))
        option = temp_option


main()


# Optimized solution
# -*- coding: utf-8 -*-

judge = 'Yes'

N = int(eval(input()))
for i in range(N):
    t, x, y = list(map(int, input().split()))
    if t < (x + y) or t % 2 != (x + y) % 2:
        judge = 'No'

print(judge)
# Original solution
n =  int(eval(input()))
for i in range(n):
    t, x, y = list(map(int, input().split()))
    if x + y > t or (x + y) % 2 != t % 2:
        print('No')
        exit()
print("Yes")

# Optimized solution
n = int(eval(input()))
for i in range(n):
    t, x, y = list(map(int, input().split()))
    if t < x + y or t % 2 != (x + y) % 2:
        print("No")
        exit()
        
print("Yes")
# Original solution
n = int(input())
txy = [list(map(int, input().split())) for i in range(n)]
loc_x=0
loc_y=0
judge=0
for i in range(n):
    if txy[i][0]%2==0:
        if (txy[i][1]+txy[i][2])%2!=0:
            judge+=1
    elif (txy[i][1]+txy[i][2])%2==0:
        judge+=1
    temp = abs(loc_x-txy[i][1])+abs(loc_y-txy[i][2])
    if i == 0:
        if temp > txy[0][0]:
            judge+=1
    else:
        if temp > txy[i][0]-txy[i-1][0]:
            judge+=1
    loc_x = txy[i][1]
    loc_y = txy[i][2]
print('No') if judge else print('Yes')


# Optimized solution
n = int(input())
txy = [list(map(int, input().split())) for i in range(n)]
loc_x=0
loc_y=0
judge=0
for i in range(n):
    if judge!=0:
        break
    if txy[i][0]%2==0:
        if (txy[i][1]+txy[i][2])%2!=0:
            judge+=1
    elif (txy[i][1]+txy[i][2])%2==0:
        judge+=1
    temp = abs(loc_x-txy[i][1])+abs(loc_y-txy[i][2])
    if i == 0:
        if temp > txy[0][0]:
            judge+=1
    else:
        if temp > txy[i][0]-txy[i-1][0]:
            judge+=1
    loc_x = txy[i][1]
    loc_y = txy[i][2]
print('No') if judge else print('Yes')
# Original solution
N=int(eval(input()))

t0=0
x0=0
y0=0

for i in range(N):
    t,x,y=list(map(int,input().split()))
    d=abs(x-x0)+abs(y-y0)
    if d>t-t0:
        print("No")
        exit()
    else:
        if ((t-t0)-d)%2!=0:
            print("No")
            exit()
    t0=t
    x0=x
    y0=y

print("Yes")

# Optimized solution
N=int(eval(input()))

t0=0
x0=0
y0=0

ans="Yes"

for i in range(N):
    t,x,y=list(map(int,input().split()))
    d=abs(x-x0)+abs(y-y0)
    dt=t-t0
    if d>dt:
        ans="No"
    else:
        if (dt-d)%2!=0:
            ans="No"
    t0=t
    x0=x
    y0=y

print(ans)
# Original solution
def c_Traveling(N, P):
    t_old = x_old = y_old = 0
    for t, x, y in P:
        t1 = t - t_old
        x1 = x - x_old
        y1 = y - y_old
        cond1 = abs(x1) + abs(y1)
        cond2 = t1 % 2
        cond3 = cond1 % 2
        if t1 >= cond1 and cond2 == cond3:
            pass
        else:
            return 'No'
        t_old, x_old, y_old = t, x, y
    return 'Yes'

N = int(eval(input()))
P = [[int(i) for i in input().split()] for j in range(N)]
print((c_Traveling(N, P)))

# Optimized solution
def c_traveling(N, P):
    t = x = y = 0  # 初期時刻には原点にいる
    for t_next, x_next, y_next in P:
        dt = t_next - t
        dd = abs(x_next - x) + abs(y_next - y)
        if dt >= dd and dt % 2 == dd % 2:
            # 制限時間は次の座標へのマンハッタン距離以上持っていないとたどり着けない
            # 制限時間と距離の偶奇が一致していないと次の座標で止まることができない
            t, x, y = t_next, x_next, y_next
        else:
            return 'No'
    return 'Yes'

N = int(eval(input()))
P = [[int(i) for i in input().split()] for j in range(N)]
print((c_traveling(N, P)))
# Original solution
import sys
input = sys.stdin.readline

class Deer:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.t = 0

    def move(self, ti, xi, yi):
        time_interval = ti - self.t
        manhattan_distance = abs(xi - self.x) + abs(yi - self.y)
        val = time_interval - manhattan_distance
        if (val >= 0) and (val % 2 == 0):
            self.x = xi
            self.y = yi
            self.t = ti
            return True
        else:
            return False

AtCoDeer = Deer()
N = int(eval(input()))
flag = True
for _ in range(N):
    ti, xi, yi = list(map(int, input().split()))
    flag = flag and AtCoDeer.move(ti, xi, yi)


if flag:
    print('Yes')
else:
    print('No')



# Optimized solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
flag = True
for _ in range(N):
    t, x, y = list(map(int, input().split()))
    if (t < x + y) or (x + y + t) % 2:
        flag = False


if flag:
    print('Yes')
else:
    print('No')
# Original solution
import sys
N = int(eval(input()))
t, x, y = 0, 0, 0
for i in range(N):
    in_t, in_x, in_y = list(map(int, input().split()))
    t = in_t - t
    x = abs(in_x - x)
    y = abs(in_y - y)
    if (t >= x + y) & ((t - (x + y)) % 2 == 0):
        continue
    print('No')
    sys.exit()
print('Yes')

# Optimized solution
import sys
N = int(eval(input()))
for _ in range(N):
    t, x, y = list(map(int, input().split()))
    if (t >= x + y) & ((t - (x + y)) % 2 == 0):
        continue
    print('No')
    sys.exit()
print('Yes')
# Original solution
n = int(eval(input()))
info = [list(map(int, input().split())) for i in range(n)]

info.insert(0, [0, 0, 0])
x_diff, y_diff = 0, 0

for i in range(n):
    dt = info[i+1][0] - info[i][0]
    x_diff = abs(info[i+1][1] - info[i][1])
    y_diff = abs(info[i+1][2] - info[i][2])
    if dt < x_diff + y_diff:
        print('No')
        exit()
    if dt%2 != (x_diff + y_diff)%2:
        print('No')
        exit()

print('Yes')


# Optimized solution
n = int(eval(input()))
for i in range(n):
    t,x,y=list(map(int,input().split()))
    if (x + y) > t or (x + y + t) % 2:
        print("No")
        exit()
print("Yes")
# Original solution
N = int(eval(input()))
T = [[0, 0]]
for _ in range(N):
    t, x, y = list(map(int, input().split()))
    T.append((t, x + y))

for i in range(N):
    dt = T[i+1][0] - T[i][0]
    dxy = abs(T[i+1][1] - T[i][1])

    if dt < dxy or dt % 2 != dxy % 2:
        print("No")
        break
else:
    print("Yes")

# Optimized solution
T = [[0, 0]]
for i in range(int(eval(input()))):
    t, x, y = list(map(int, input().split()))
    T.append((t, x + y))

    dt = T[i+1][0] - T[i][0]
    dxy = abs(T[i+1][1] - T[i][1])

    if dt < dxy or dt % 2 != dxy % 2:
        print("No")
        break
else:
    print("Yes")
# Original solution
import math
import sys

n = int(eval(input()))

for i in range(n):
	t,x,y = list(map(int, input().split()))
	d = abs(x)+abs(y)

	if d > t or (d - t) % 2 != 0:
		print('No')
		exit()

print('Yes')


# Optimized solution
import math
import sys

n = int(eval(input()))

for i in range(n):
	t,x,y = list(map(int, sys.stdin.readline().split()))
	d = abs(x)+abs(y)

	if d > t or (d - t) % 2 != 0:
		print('No')
		exit()

print('Yes')
# Original solution
N = int(eval(input()))
now_x = 0
now_y = 0
now_t = 0
Flag = False
for i in range(N):
    t , x, y = list(map(int,input().split()))
    dx = abs(x - now_x)
    dy = abs(y - now_y)
    dt = abs(t - now_t)
    if (dt - (dx + dy)) % 2 != 0 or dt < (dx + dy):
        Flag = True
    now_x = x
    now_y = y
    now_t = t
print(("No" if Flag else "Yes"))

# Optimized solution
N = int(eval(input()))
now_t, now_x, now_y = 0, 0, 0
for i in range(N):
    next_t, next_x, next_y = list(map(int, input().split()))
    distance = abs(next_x - now_x) + abs(next_y - now_y)
    spent_time = next_t - now_t
    if spent_time < distance or distance % 2 != spent_time % 2:
        print('No')
        exit()
    now_t, now_x, now_y = next_t, next_x, next_y
print('Yes')
# Original solution
n = int(eval(input()))
t = 0
x = 0
y = 0
judge = True

for i in range(n):
    t1, x1, y1 = list(map(int, input().split()))
    if (abs(x1 - x) + abs(y1 - y))/(t1 - t) > 1 or (abs(x1 - x) + abs(y1 - y))%2 != (t1 - t)%2:
        judge = False
    x = x1
    y = y1
    t = t1

if judge == True:
    print("Yes")
else:
    print("No")

# Optimized solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
t = 0
x = 0
y = 0
judge = True

for i in range(n):
    t1, x1, y1 = list(map(int, input().split()))
    if (abs(x1 - x) + abs(y1 - y))/(t1 - t) > 1 or (abs(x1 - x) + abs(y1 - y))%2 != (t1 - t)%2:
        judge = False
    x = x1
    y = y1
    t = t1

if judge == True:
    print("Yes")
else:
    print("No")
# Original solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
t = 0
x = 0
y = 0
judge = True

l = [list(map(int, input().split())) for _ in range(n)]

for t1, x1, y1 in l:
    if (abs(x1 - x) + abs(y1 - y))/(t1 - t) > 1 or (abs(x1 - x) + abs(y1 - y))%2 != (t1 - t)%2:
        print("No")
        exit()
    x = x1
    y = y1
    t = t1

print("Yes")

# Optimized solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
t = 0
x = 0
y = 0
judge = True

l = [tuple(map(int, input().split())) for _ in range(n)]

for t1, x1, y1 in l:
    if (abs(x1 - x) + abs(y1 - y))/(t1 - t) > 1 or (abs(x1 - x) + abs(y1 - y))%2 != (t1 - t)%2:
        print("No")
        exit()
    x = x1
    y = y1
    t = t1

print("Yes")
# Original solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
t = 0
x = 0
y = 0

l = [tuple(map(int, input().split())) for _ in range(n)]

for t1, x1, y1 in l:
    if (abs(x1 - x) + abs(y1 - y))/(t1 - t) > 1:
        print("No")
        exit()
    if (abs(x1 - x) + abs(y1 - y))%2 != (t1 - t)%2:
        print("No")
        exit()
    x = x1
    y = y1
    t = t1

print("Yes")

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    t = 0
    x = 0
    y = 0

    l = [tuple(map(int, input().split())) for _ in range(n)]

    for t1, x1, y1 in l:
        if (abs(x1 - x) + abs(y1 - y))/(t1 - t) > 1:
            print("No")
            exit()
        if (abs(x1 - x) + abs(y1 - y))%2 != (t1 - t)%2:
            print("No")
            exit()
        x = x1
        y = y1
        t = t1

    print("Yes")
main()
# Original solution
n=int(input())
txy=[]
for _ in range(n):
    t,x,y=map(int, input().split())
    txy.append((t,x,y))

def isOk(txy):
    now_pos=0
    now_t=0

    for t,x,y in txy:
        move=x+y-now_pos
        time=t-now_t
        if time>=move and time%2==move%2:
            continue
        else:
            return False
    return True

print("Yes") if isOk(txy) else print("No")


# Optimized solution
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
TXY = [list(map(int, input().split())) for _ in range(N)]

nx, ny = 0, 0
time = 0

ans = "Yes"
for i in range(N):
    t, x, y = TXY[i]
    dt = t - time
    move = abs(nx - x) + abs(ny - y)
    if move > dt:
        ans = "No"
        break
    if dt % 2 != move % 2:
        ans = "No"
        break
    time, nx, ny = t, x, y

print(ans)
# Original solution
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a_root]
            b_member = member[b_root]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
    
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
    
    def operation(line):
        if line[0] == '!':
            a, b, w = map(int, line[2:].split())
            measurement(a, b, w)
        else:
            a, b = map(int, line[2:].split())
            return inquiry(a, b)
    
    import sys
    file_input = sys.stdin.readlines()
    
    while True:
        N, M = map(int, file_input[0].split())
        if N == 0:
            break
        
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
        
        ans = (operation(line) for line in file_input[1:M+1])
        ans = filter(lambda x: x != None, ans)
        print(*ans, sep='\n')
        
        del file_input[:M+1]

solve()


# Optimized solution
def solve():
    def measurement(a, b, w):
        a_root = root[a]
        b_root = root[b]
        if a_root != b_root:
            a_member = member[a_root]
            b_member = member[b_root]
            offset = w - (weight[b] - weight[a])
            if len(a_member) > len(b_member):
                a_member.extend(b_member)
                for n in b_member:
                    root[n] = a_root
                    weight[n] += offset
            else:
                b_member.extend(a_member)
                for n in a_member:
                    root[n] = b_root
                    weight[n] -= offset
     
    def inquiry(a, b):
        if root[a] == root[b]:
            return weight[b] - weight[a]
        else:
            return 'UNKNOWN'
                     
    import sys
    file_input = sys.stdin.readlines()
    ans = []
     
    while True:
        N, M = map(int, file_input[0].split())
        if N == 0:
            break
         
        root = [i for i in range(N + 1)]
        member = [[i] for i in range(N + 1)]
        weight = [0] * (N + 1)
         
        for line in file_input[1:M+1]:
            if line[0] == '!':
                a, b, w = map(int, line[2:].split())
                measurement(a, b, w)
            else:
                a, b= map(int, line[2:].split())
                ans.append(inquiry(a, b))
         
        del file_input[:M+1]
    
    print(*ans, sep='\n')
 
solve()
# Original solution
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]*num_t[v])**2
        ans%=mod
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=(num_t[v]*num_s[v])**2
        ans%=mod
print((ans%mod))







# Optimized solution
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))
# Original solution
from collections import defaultdict
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = list(map(int,stdin.readline().split()))
S,T = list(map(int,stdin.readline().split()))
S,T = S-1,T-1
 
E = defaultdict(list)
lines = stdin.readlines()
for line in lines:
  u,v,d = list(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, [x*x % MOD for x in X],0)
print(((total-sub)%MOD))

# Optimized solution
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = list(map(int,stdin.readline().split()))
S,T = list(map(int,stdin.readline().split()))
S,T = S-1,T-1

inf = float('inf')
 
E = [[] for _ in range(N)]
lines = stdin.readlines()
for line in lines:
  u,v,d = list(map(int,line.split()))
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))
 
dS = [inf]*N
dT = [inf]*N
 
Q = [(0,S,False),(0,T,True)]

D = 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] > d:
    dM[v] = d
    for u,dd in E[v]:
      if dM[u] > d and (d+dd)*2 <= D:
        hq.heappush(Q,(d+dd,u,f))
   
  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 != inf):
    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] != inf:
      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 abs(dT[u]-ds) < d and ds+d+dT[u] == D:
            yield Sn[v]*Tn[u] % MOD


X = tuple(it())
 
total = reduce(lambda a,b:(a+b)%MOD, X,0)
total = total*total % MOD
 
sub = reduce(lambda a,b:(a+b)%MOD, [x*x % MOD for x in X],0)

print(((total-sub)%MOD))
# Original solution
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 = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn, vn = divmod(k, geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df, vf = divmod(k, geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)*geta)+vf)
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = list(map(int, readline().split()))
S, T = list(map(int, readline().split()))
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = list(map(int, readline().split()))
    u -= 1
    v -= 1
    Edge[u].append(d*geta+v)
    Edge[v].append(d*geta+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 k in Edge[i]:
        cost, vf = divmod(k, geta)
        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)


# Optimized solution
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 = list(map(int, readline().split()))
S, T = list(map(int, readline().split()))
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = list(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)