Harryxun/stf_run huggingface dataset:
N = int(input())
total = 0
tmp = 0
A = []
xy = []
l = []
for i in range(N):
  A.append(int(input())
  for j in range(A[i]):
    l.append(list(map(int,input().split())))
  xy.append(l)
  l.clear()
for i in range(2**N):
  flag = 1
  t = format(i, '0{}b'.format(N))
  for k in range(N):
    if t[k] == '1':
      tmp += 1
      for l in range(A[k]):
        if int(t[xy[k][l][0]-1]) != xy[k][l][1]:
          flag = 0
          break
      else:
        continue
      break
  if flag == 1 and total < tmp:
    total = tmp
  tmp = 0
print(total)
          


### FIXED CODE ###

#標準入力受け取り
N = int(input())
shougen = []
A_lis = []
for _ in range(N):
    A = int(input())
    A_lis.append(A)
    minishougen = []
    for j in range(A):
        xy = list(map(int, input().split()))
        minishougen.append(xy)
    shougen.append(minishougen)

#ビットの配列作る
bit_lis = []
for i in range(2 ** N):
    mini_bit_lis = []
    for j in range(N):
        mini_bit_lis.append(i % 2)
        i = i // 2
    bit_lis.append(mini_bit_lis)
    
#ビットの配列について全探索を行う
ans = 0
for i in range(2 ** N):
    flag = 0
    for l in range(N):
        if bit_lis[i][l] == 1:
            for k in range(A_lis[l]): 
                if shougen[l][k][1] != bit_lis[i][shougen[l][k][0] - 1]:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = sum(bit_lis[i])
        if tmp > ans :
            ans = tmp
print(ans)
n = int(input())
a = list(map(int,input().split()))

tmp = 0
for i in a:
   tmp += 1/a 

print(1/tmp)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
     
tmp = 0
for i in a:
    tmp += 1/i

print(1/tmp)
#!/usr/bin/python3

n = int(input())
a = [int(_) for _ in input().split()]

p = a[0]
q = a[1]
r = a[2]
s = 0
for i in range(3, n):
    s += a[i]

d1 = 0
d3 = 2
while s - r > a[d3]:
    d3 += 1
    r += a[d3]
    s -= a[d3]

ans = float('inf')
for d2 in range(1, n - 1):
    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))
    q += a[d2 + 1]
    while q - p > a[d1]:
        if d1 + 1 == d2 + 1:
            break
        d1 += 1
        p += a[d1]
        q -= a[d1]
    r -= a[d2 + 1]
    if d2 + 1 == d3:
        d3 += 1
        r += a[d3]
        s -= a[d3]
    while s - r > a[d3]:
        if d3  == n - 1:
            break
        d3 += 1
        r += a[d3]
        s -= a[d3]

print(ans)


### FIXED CODE ###

#!/Library/Frameworks/Python.framework/Versions/3.5/bin/python3

n = int(input())

if n % 2 == 1:
    print(n * 2)
else:
    print(n)
import math
A, B, C = list(map(int, input().split()))
K = int(input())
#A, B, C = [7, 4, 2]
#K = 3

i = math.floor(A/(B+1))
K -= i
B = B * (2 ** i)
j = math.floor(B/(C+1))
K -= j
C = C * (2 ** j)
if K >= 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
#N, K = 5, 3
#A = [96, 98, 95, 100, 20]
#N, K = 3, 2
#A = [1001, 869120, 1001]
#N, K = 15, 7
#A = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

def getA(i):
    if i < 0:
        return 1
    elif i >= N:
        return 1
    else:
        return A[i]
# 
for i in range(K,N):
    #print(i,getA(i-K), getA(i))
    if getA(i-K) < getA(i):
        print("Yes")
    else:
        print("No")
import sys

n, s = sys.stdin.read().split()

def main():
    cnt = s.count('E')
    cur = 'E'
    res = cnt
    for c in s:
        if cur == 'W': cnt += 1
        if c == 'E': cnt -= 1
        res = min(res, cnt)
        cur = c
    print(min(res))
    
if __name__ ==  '__main__':
    main()

### FIXED CODE ###

#                         author:  kagemeka 
#                         created: 2019-11-07 23:33:56(JST)
## internal modules
import sys
import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator
## external modules
# import scipy.special   # if use comb function on AtCoder, 
# import scipy.misc      # select scipy.misc.comb (old version) 

def main():
    n = int(sys.stdin.readline().rstrip())
    s = sys.stdin.readline().rstrip()

    opposite = collections.Counter(s)
    opposite['W'] = 0
    minimum = n
    for i in range(n):
        if s[i] == 'E':
            opposite['E'] -= 1
        minimum = min(minimum, sum(opposite.values()))
        if s[i] == 'W':
            opposite['W'] += 1
    print(minimum)




if __name__ == "__main__":
    # execute only if run as a script
    main()
# -*- coding: utf-8 -*-
import sys

N,M = map( int, input().split() )

#str_lines = [x.strip("\n") for x in sys.stdin.readlines()]

list_str_P_S = [input().split() for i in range(M)]

#-----
#-----

list_question_no=list(set(list(zip(*list_str_P_S))[0]))

#print("list_str_P_S=",list_str_P_S)
#print("list_question_no=",list_question_no)

count_AC=0
count_WA=0
list_temp=[]
list_next=[]
for str_i in list_question_no:

  for L in list_str_P_S:
    str_number = L[0]
    result = L[1]
    
    if str_number == str_i:
      list_temp.append(L)
    else:
      list_next.append(L)
  #print("list_temp",list_temp)
  #print("list_next",list_next)
  

  for L in list_temp:
    str_number = L[0]
    result = L[1]
    
    if str_number == str_i:
      if result == "WA":
        count_WA += 1
        #print("L",L,count_AC,count_WA)
      elif result == "AC":
        count_AC += 1
        #print("L",L,count_AC,count_WA)
        break
        
  list_str_P_S=list_next
  list_temp=[]
  list_next=[]
  #print("list_str_P_S next=",list_str_P_S)  
  #print("-----")

#print("ans=",count_AC,count_WA)
print(count_AC,count_WA)


### FIXED CODE ###

# -*- coding: utf-8 -*-

N,M = list(map(int, input().rstrip().split()))
pS_list = []

for i in range(M):
    inp = input().rstrip().split()
    pS_list.append( [int(inp[0]), inp[1]] )

#-----
problem_AC_set = set()
problem_WA_dic = {}

for p,S in pS_list:
    if (S == "AC") and (p not in problem_AC_set):
        problem_AC_set.add(p)
    
    if (S == "WA") and (p not in problem_AC_set):
        problem_WA_dic.setdefault(p, 0)
        problem_WA_dic[p] += 1

cnt_AC = len(problem_AC_set)
cnt_WA = sum([v for k,v in problem_WA_dic.items() if k in problem_AC_set])

print(cnt_AC, cnt_WA)
N = int(input())
H = list(map(int,input().split()))
M = max(H)
count=1
i = 1
while True:
  if(H[i]==M):
    break
  else:
    judge=0
    for j in range(i):
      if(H[j]>H[i]):
        judge = judge + 1
      else:
        None
    if(judge==0):
      count += 1
  i += 1
print(count)
  
  
  

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
count = 1
for i in range(1,N):
  judge = 0
  for j in range(i):
    if(H[j]>H[i]):
      judge = judge +1
      break
  if(judge==0):
    count=count+1
print(count)
60 88 34
92 41 43
65 73 48
10
60
43
88
11
48
73
65
41
92
34


### FIXED CODE ###

b = []
b.append([int(s) for s in input().split()])
b.append([int(s) for s in input().split()])
b.append([int(s) for s in input().split()])

n = int(input())

for i in range(0, n):
    v = int(input())

    for i in range(0, 3):
        for j in range(0, 3):
            if b[i][j] == v:
                b[i][j] = 999

ans = 'No'

for i in range(0, 3):
    s = set(b[i])

    if len(s) == 1:
        ans = 'Yes'

for i in range(0, 3):
    s = set([b[0][i], b[1][i], b[2][i]])

    if len(s) == 1:
        ans = 'Yes'

c = set([b[0][0], b[1][1], b[2][2]])

if len(c) == 1:
    ans = 'Yes'

c = set([b[0][2], b[1][1], b[2][0]])

if len(c) == 1:
    ans = 'Yes'

print(ans)
N = int(input())
S = str(input())

if N % 2 == 0:
    T = S[:N/2]
    if S == T + T:
        print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
S = str(input())

if N % 2 == 0:
    T = S[:int(N/2)]
    if S == T + T:
        print('Yes')
    else:
      print('No')
else:
    print('No')
import functools
n = int(input())

def gcd(nums):
    return functools.reduce(euclid, nums)

a = 0

for i in range(n):
  for j in range(n):
    for k in range(n):
      num = [i+1, j+1, k+1]
      a = a + gcd(num)
      
print(a)

### FIXED CODE ###

import math
n = int(input())

a = 0
 
for i in range(n):
  for j in range(n):
    for k in range(n):
      t = math.gcd(i+1, j+1)
      a = a + math.gcd(t, k+1)
      
print(a)
N = str(input())

print(N.replace('1', '9').replace('9', '1')

### FIXED CODE ###

N = input()
L = list(N)

for i in range(3):
  if L[i] == "1":
    L[i] = "9"
  else:
    L[i] = "1"
print("".join(L))
H, W = map(int, input().split())
px = []
ans = []
for x in range(H):
    px.append(W[x])
    px.append(W[x])

print(px)

### FIXED CODE ###

H, W = map(int, input().split())
px = []
ans = []
for x in range(H):
    px.append(input())
    ans.append(px[x])
    ans.append(px[x])

for x in range(len(ans)):
    print(ans[x])
a,b,c = map(int,input().split())
if a=b and b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


### FIXED CODE ###

a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)
l, r = map(int, input().split())

from itertools import combinations

ans = 2019

for (x1, x2) in combinations(range(l, r+1), 2):
    a = (x1 * x2) % 2019
    if a < ans:
        ans = a

print(ans)


### FIXED CODE ###

l, r = map(int, input().split())

from itertools import combinations

if r - l > 2019:
    r = l+2019

ans = [(x1*x2)%2019 for (x1, x2) in combinations(range(l, r+1), 2)]

print(min(ans))
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)


### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if k >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)
n = int (input())
for i in range(1,n):
  result =result + i
print result

### FIXED CODE ###

n = int (input())
result =0
for i in range(1,n+1):
    result =result +i
print (result)
n = input()
a = input()
a = a.split(sep=' ')

result = 0
for i in range(1,int(n)+1):
    if int(a[int(a[i])]) == i:
        result = result+1
result = int(result/2)
print(result)

### FIXED CODE ###

n = input()
a = input()
a = a.split(sep=' ')

result = 0
for i in range(1,int(n)+1):
    if int(a[int(a[i-1])-1]) == i:
        result = result+1
result = int(result/2)
print(result)
a,b,c=map(int,input().split( ))
for i in range(0,9):
  c=a*c-b
  print c

### FIXED CODE ###

a,b,c=(int(i) for i in input().split())
for i in range(10):
  c=a*c-b
  print(c)
A = input()
Len = len(A)
L = (Len // 2) + (Len % 2)
count = 0
for i in range(4):
  if A[i] != A[-i-1]:
    count += 1
print(count)

### FIXED CODE ###

A = input()
Len = len(A)
L = (Len // 2) + (Len % 2)
count = 0
for i in range(L):
  if A[i] != A[-i-1]:
    count += 1
print(count)
strings = raw_input.split(',')
new_strings = []
for string in strings:
  if string.islower():
    new_strings.append(string.upper())
  else:
    new_strings.append(string.lower())
for new_string in new_strings:
  print new_string + ',',

### FIXED CODE ###

print raw_input().swapcase()
a=input()
if a=='a' or a=='i' or a=='u' or a=='e' a=='o':
  print('vowel')
else:
  print('consonant')

### FIXED CODE ###

a=input()
if a=='a' or a=='i' or a=='u' or a=='e' or a=='o':
  print('vowel')
else:
  print('consonant')
mask = [range(6), (1, 5, 2, 3, 0, 4), (2, 1, 5, 0, 4,3),(3, 1, 0, 5, 4, 2), (4, 0, 2, 3, 5, 1)]
mask += [mask[1][i] for i in mask[1]]

TOP, FRONT, RIGHT, LEFT, BACK, BOTTOM = mask[0]

def set_top(dice, top):
    return [dice[i] for i in mask[top]]

def set_front(dice, front):
    twist = (0, 3, 1, 4, 2, 5)
    while dice[FRONT] != front:
        dice = [dice[i] for i in twist]
    return dice
        
label = input().split()
q = int(input())
for _ in range(q):
    top, front = map(label.index, input().split())
    dice = set_top(mask[0], top)
    dice = set_front(dice, front)
    print(label[dice[RIGHT]])

### FIXED CODE ###

mask = [[i for i in range(6)], (1, 5, 2, 3, 0, 4), (2, 1, 5, 0, 4,3),(3, 1, 0, 5, 4, 2), (4, 0, 2, 3, 5, 1)]
mask += [[mask[1][i] for i in mask[1]]]

TOP, FRONT, RIGHT, LEFT, BACK, BOTTOM = mask[0]

def set_top(dice, top):
    return [dice[i] for i in mask[top]]

def set_front(dice, front):
    twist = (0, 3, 1, 4, 2, 5)
    while dice[FRONT] != front:
        dice = [dice[i] for i in twist]
    return dice
        
label = input().split()
q = int(input())
for _ in range(q):
    top, front = map(label.index, input().split())
    dice = set_top(mask[0], top)
    dice = set_front(dice, front)
    print(label[dice[RIGHT]])
INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
        # 一度も更新されなければ終了
        if not update:
            break
    return dist

def find_negative_loop(n, es):
    dist = [0] * n
    for i in range(n):
        for e in es:
            if dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                if i == n - 1:
                    return True
    return False

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))



if find_negative_loop(N, es): # cost < 0 の辺で行き来できる場合も負の閉路になる
  print('inf')
  print(1/0)
else:
  print(-bellman_ford(N, es,0)[N-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    cnt = 0
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        # 一度も更新されなければ終了
        if not update or cnt == n:
            break
    return dist

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))


print(-bellman_ford(N, es,0)[N-1])
n,m,c = map(int,input().split())
input_b = map(int,input().split())
a_list=[input() for i in range(n)]
for i in range(n):
  answer = c
  count = 0
  aitems = map(int,a_list[i].split())
  for j in range(m):
    answer += input_b[j] * aitems[j]
  if answer > 0:
    count+=1
print count

### FIXED CODE ###

n,m,c = map(int,input().split())
input_b = list(map(int,input().split()))
a_list=[input() for i in range(n)]
count = 0
for i in range(n):
  answer = c
  aitems = list(map(int,a_list[i].split()))
  for j in range(m):
    answer += input_b[j] * aitems[j]
  if answer > 0:
    count+=1
print(count)
a, b = map(int, input().split())
n = int(input())
print(n // (a + b) + min(n % (a + b), a))

### FIXED CODE ###

N, A, B = map(int, input().split())

result = 0
result += N // (A + B) * A
result += min(N % (A + B), A)
print(result)
n = int(input())
a = list(int(i) for i in input().split())

hai = 0
tya = 0
midori = 0
mizu = 0
ao = 0
ki = 0
daigai = 0
aka = 0

niji = 0

mincolor = 0
maxcolor = 0

for i in range(n):
    if 1 <= a[i] and a[i] <=399:
        hai = 1
    elif 400 <= a[i] and a[i] <= 799:
        tya = 1
    elif 800 <= a[i] and a[i] <= 1199:
        midori
    elif 1200 <= a[i] and a[i] <=1599:
        mizu = 1
    elif 1600 <= a[i] and a[i] <= 1999:
        ao = 1
    elif 2000 <= a[i] and a[i] <= 2399:
        ki = 1
    elif 2400 <= a[i] and a[i] <=2799:
        daidai = 1
    elif 2800 <= a[i] and a[i] <= 3199:
        aka = 1
    elif 3200 <= a[i]:
        niji += 1

mincolor = hai + tya + midori + mizu + ao + ki + daidai + aka
maxcolor = mincolor

for i in range(niji):
    maxcolor += 1

if maxcolor >= 9:
    maxcolor = 8

print(mincolor, maxcolor)


### FIXED CODE ###

n = int(input())
a = list(int(i) for i in input().split())

hai = 0
tya = 0
midori = 0
mizu = 0
ao = 0
ki = 0
daidai = 0
aka = 0

niji = 0

for i in range(n):
    if 1 <= a[i] and a[i] <=399:
        hai = 1
    elif 400 <= a[i] and a[i] <= 799:
        tya = 1
    elif 800 <= a[i] and a[i] <= 1199:
        midori = 1
    elif 1200 <= a[i] and a[i] <=1599:
        mizu = 1
    elif 1600 <= a[i] and a[i] <= 1999:
        ao = 1
    elif 2000 <= a[i] and a[i] <= 2399:
        ki = 1
    elif 2400 <= a[i] and a[i] <=2799:
        daidai = 1
    elif 2800 <= a[i] and a[i] <= 3199:
        aka = 1
    elif 3200 <= a[i]:
        niji += 1

mincolor = hai + tya + midori + mizu + ao + ki + daidai + aka

if mincolor == 0:
    mincolor += 1
    niji -= 1

maxcolor = mincolor + niji

#if maxcolor >= 9:
#    maxcolor = 8

print(mincolor, maxcolor)
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 32
    inf = 1<<geta
    dist = [inf] * N
    dist[s] = 0
    Q = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn = k>>geta
        vn = k^(dn<<geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df = k>>geta
            vf = k^(df<<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 = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 32
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = 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*ditt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for k in Edge[i]:
        cost = k>>geta
        vf = k^(cost<<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)

### FIXED CODE ###

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)
# -*- coding: utf-8 -*-
N,A,B =map(int,input(),split())
if (A * N) > B:
  print(B)
else:
  print(A*N)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N,A,B = map(int,input().split())
if A * N >= B:
  print(B)
else:
  print("{}".format(A*N))
H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import numpy as np


A = np.array(A)
WK = np.zeros(A.shape)
i = 0
S = H * W
while True:
    if np.min(A) == 1:
        break
    WK -= WK
    WK += A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A[:,:-1] |= WK[:,1:]
    A[:,1:] |= WK[:,:-1]
    i += 1

print(i)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)