Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    a, c = [], []
    for i in range(M):
        t, _ = map(int, input().split())
        a.append(t)
        cc = set(map(int, input().split()))
        c.append(cc)

    al = set(range(1, N + 1))
    print(helper(0, N, M, a, c, 0, al))

def helper(i, N, M, a, c, price, al):
    if not al:
        return price
    if i == M:
        return -1
    t = helper(i + 1, N, M, a, c, price + a[i], al - c[i])
    s = helper(i + 1, N, M, a, c, price, al)
    if t != -1 and s != -1:
        return min(t, s)
    else:
        return max(t, s)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    cd = {}
    FAIL = (10 ** 3) * (10 ** 5) + 1
    for _ in range(M):
        ai, _ = map(int, input().split())
        ci = sum(1 << (int(i) - 1) for i in input().split())
        keys = list(cd.keys())
        for i in keys:
            cd[i | ci] = min(cd.get(i | ci, FAIL), cd[i] + ai)
        cd[ci] = min(cd.get(ci, FAIL), ai)
    print(cd.get((1 << N) - 1, -1))


if __name__ == '__main__':
    main()
N,K=input()
if N%K==0:
  print("0")
else:
  print("1")

### FIXED CODE ###

N, K = map(int, input().split())
if N%K==0:
  print(0)
else:
  print(1)
X, N = list(map(int,input().split()))
if N !=0:
  P = list(map(int,input().split()))
  ab = 100
  for i in range(101):
    if i not in P:
      if abs(X-i)<ab:
        ab = abs(X-i)
        ans = i
      elif abs(X-i)==ab:
        ans = min(ans,i)
  print(ans)
else:
  print(X)
    

### FIXED CODE ###

X, N = list(map(int,input().split()))
if N !=0:
  P = list(map(int,input().split()))
  ab = 100
  for i in range(-100,200):
    if i not in P:
      if abs(X-i)<ab:
        ab = abs(X-i)
        ans = i
  print(ans)
else:
  print(X)
n = int(input())
 
if n == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(A+B)

### FIXED CODE ###

n = int(input())
 
if n == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(a+b)
n=int(input())
l=list(map(int,input().split()))
dp=[10**55 for i in range(n)]
dp[0]=0
dp[1]=abs(l[1]-l[0])
for i in range(2,n):
    dp[i] = min(dp[i], dp[i-1] + abs(l[i] - l[i - 1]))
    dp[i] = min(dp[i], dp[i-2] + abs(l[i] - l[i - 2]))
    print(dp)
print(dp[n-1])



### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
dp=[10**55 for i in range(n)]
dp[0]=0
dp[1]=abs(l[1]-l[0])
for i in range(2,n):
    dp[i] = min(dp[i], dp[i-1] + abs(l[i] - l[i - 1]))
    dp[i] = min(dp[i], dp[i-2] + abs(l[i] - l[i - 2]))
print(dp[n-1])
st = input()

def find_bw(s):
  k = 0
  temp = False
  while True:
    if s[k] == "B":
      while True:
        if s[k] == "W":
          temp = True
          break
        k+= 1
    if temp:
      break
    k+=1
    if k>len(s):
      break
  return k

print(find_bw(st))

### FIXED CODE ###

b = input()
white = 0
bl = []
for k in b:
    if k == 'B':
        bl.append(1)
    else:
        white += 1
        bl.append(0)
k = 0
wp = white
ans = 0
for p in bl:
    if p==1:
        ans += wp - k
        wp += 1
    k += 1

print(ans)
a, b, c = input().split()

if a < b and b < c:
  print('No')

if a < c and c < b:
  print('Yes')

if b < c and c < a:
  print('Yes')

if b < a and a < c:
  print('No')
  
if c < a and a < b:
  print('Yes')
  
if c < b and b < a:
  print(No)

### FIXED CODE ###

a, b, c = input().split()
if (int(a) < int(c) and int(c) < int(b)) or (int(b) < int(c) and int(c) < int(a)):
  print('Yes')
else:
  print('No')
def f(x):
    ret = 0
    while x != 0:
        ret += x%10
        x //= 10
    return ret

n = int(input())
print("Yes" if x % f(x) == 0 else "No")

### FIXED CODE ###

def f(x):
    ret = 0
    while x != 0:
        ret += x%10
        x //= 10
    return ret

n = int(input())
print("Yes" if n % f(n) == 0 else "No")
k = input()
a, b = map(int, input().split())
if b//k - a//k <= 0 or b - a >= 0:
  print("OK")
else:print("NG")

### FIXED CODE ###

k = int(input())
a, b = map(int, input().split())
ka = a // k
kb = b // k
if b - a >= k - 1:
  print("OK")
elif kb - ka > 0:
  print("OK")
elif a % k == 0 or b % k == 0:
  print("OK")
else:
  print("NG")
if __name__=='__main__':
    a = input()
    b = input()

    day = int(a)-1
    if b >= a:
        day += 1
    print(day)

### FIXED CODE ###

if __name__=='__main__':
    a, b = map(int, input().split())

    day = int(a)-1
    if b >= a:
        day += 1
    print(day)
import bisect
import numpy

n, m, k = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
b = list(map(int, input().split(" ")))

cost_a = numpy.insert(numpy.cumsum(a), 0, 0)
cost_b = numpy.insert(numpy.cumsum(b), 0, 0)

ans = 0
j =  len(cost_b) -1
for i in range(len(cost_a)):
    for j in range( j, 0, -1):
        if cost_a[i] + cost_b[j] <= k:
            ans  = i + j if ans < i + j else ans
            break
print(ans)
[root@local

### FIXED CODE ###


import bisect
import numpy

n, m, k = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
b = list(map(int, input().split(" ")))

cost_a = numpy.insert(numpy.cumsum(a), 0, 0)
cost_b = numpy.insert(numpy.cumsum(b), 0, 0)

ans = 0
j =  len(cost_b) -1
for i in range(len(cost_a)):
    for j in range(j, -1, -1):
        if cost_a[i] + cost_b[j] <= k:
            ans  = i + j if ans < i + j else ans
            break
print(ans)
from colletions import Counter

N = int(input())
d = Counter(map(int, input().split()))

sticks_len = []
for k, v in d:
  if v >= 2:
    sticks.append(k)
  if v >= 4:
    sticks.append(k)
    
sticks.sort()

if len(sticks) >= 2:
  print(sticks[-1] * sticks[-2])
else:
  print(0)

  


### FIXED CODE ###

from collections import Counter
 
N = int(input())
d = Counter(map(int, input().split()))
 
sticks_len = []
for k, v in d.items():
  if v >= 2:
    sticks_len.append(k)
  if v >= 4:
    sticks_len.append(k)
    
sticks_len.sort()
 
if len(sticks_len) >= 2:
  print(sticks_len[-1] * sticks_len[-2])
else:
  print(0)
n=int(input())
a=list(map(int,input().split()))
a.sort()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
if len(minus)==0:
    print(a[-1]-a[0]+sum(a[1:n-1]))
    for i in range(n):
        if i==n-2:
            print(a[-1],a[n-2])
        else:
            print(a[i],a[i+1])
            a[i+1]=a[i]-a[i+1]
elif len(plus)==0:
    print(a[-1]-a[0]-sum(a[1:n-1]))
    print(a[-1],a[0])
    a[-1]=a[-1]-a[0]
    for i in range(1,n-1):
        print(a[-1],a[i])
        a[-1]-=a[i]
else:
    print(a[-1]-a[0]-sum(minus[1:-1])+sum(plus[0:-1]))
    for i in range(len(plus)-1):
        print(a[0],plus[i])
        a[0]-=plus[i]
    for i in range(0,len(minus)):
        print(a[-1],minus[i])
        a[-1]-=minus[i]

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
if len(minus)==0:
    print(a[-1]-a[0]+sum(a[1:n-1]))
    for i in range(n-1):
        if i==n-2:
            print(a[-1],a[n-2])
        else:
            print(a[i],a[i+1])
            a[i+1]=a[i]-a[i+1]
elif len(plus)==0:
    print(a[-1]-a[0]-sum(a[1:n-1]))
    print(a[-1],a[0])
    a[-1]=a[-1]-a[0]
    for i in range(1,n-1):
        print(a[-1],a[i])
        a[-1]-=a[i]
else:
    print(a[-1]-a[0]-sum(minus[1:])+sum(plus[0:-1]))
    for i in range(len(plus)-1):
        print(minus[0],plus[i])
        minus[0]-=plus[i]
    for i in range(len(minus)):
        print(a[-1],minus[i])
        a[-1]-=minus[i]
w=input()
c=0
while True:
    t=input().lower()
    if t=='END_OF_TEXT':
        print(c)
        break
    c+=t.lower().split().count(w)


### FIXED CODE ###

w=input()
c=0
while True:
    t=input()
    if t=='END_OF_TEXT':
        print(c)
        break
    c+=t.lower().split().count(w)
a, b, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
XYC = [list(map(int, input().split())) for _ in range(m)]

mn = min(A) + min(B)

for x, y, c in XYC:
    mn = min(mn, A[x - 1] + B[x - 1] - c)
print(mn)

### FIXED CODE ###

a, b, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
XYC = [list(map(int, input().split())) for _ in range(m)]

mn = min(A) + min(B)

for x, y, c in XYC:
    mn = min(mn, A[x - 1] + B[y - 1] - c)
print(mn)
n,  m = map(int, input().split())
np = [input() for _ in range(n)]
mp = [input() for _ in range(m)]
for i in range(n-m-1):
  for  j in range(n-m-1):
    f = True
    for k in range(m):
      if np[i+k][j:j+m] != mp[i+k]:
        f = False
    if f:
      print("Yes")
      exit(0)
else:
  print("No")

### FIXED CODE ###

n,  m = map(int, input().split())
np = [input() for _ in range(n)]
mp = [input() for _ in range(m)]
for i in range(n-m+1):
  for j in range(n-m+1):
    f = True
    for k in range(m):
      if np[i+k][j:j+m] != mp[k]:
        f = False
    if f:
      print("Yes")
      exit(0)
else:
  print("No")
r = int(input())

c = r * r *3.141592653589

print("{0:.6f}".format(c))

### FIXED CODE ###

import math
r = float(input())

c = r * r *math.pi
cf = r *2 *math.pi

a = ("{0:.5f} {1:.5f}".format(c,cf))

print(a)
N, K = map(int, input().split())
x = N % K

print(min(x, abs(x - K))

### FIXED CODE ###

N, K = map(int, input().split())
x = N % K
print(min(x, abs(x - K)))
from fraction import gcd
n = int(input())
A = list(map(int,input().split()))
left = [0]*(n+1)
right = [0]*(n+2)
for a,aa,i in zip(A,A[::-1],range(1,n+1)):
    left[i] = gcd(a,left[i-1])
    right[n+1-i] = gcd(aa,right[n-i+2])
ans = 1
for i in range(1,n+1):
    if i ==1:
        if ans < right[i+1]:
            ans = right[i+1]
    elif i == n:
        if ans < left[i-1]:
            ans = left[i-1]
    else:
        if ans < gcd(left[i-1],right[i+1]):
            ans = gcd(left[i-1],right[i+1])

print(ans)
    

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()
def find(inte):
    re = []
    for i in range(1,int(inte**0.5)+1):
        if inte%i==0:
            re.append(i)
            if i != inte/i:
                re.append(int(inte/i))
    return set(re)
if n==2:
    print(A[1])
else:
    a1 = find(A[0])
    a2 = find(A[1])
    a3 = find(A[2])
    t1 = a1 & a2
    t2 = a2 & a3
    t3 = a1 & a3
    cond = t1 | t2 |t3
    maxi = 0
    for con in cond:
        count = 0
        flag = True
        for a in A:
            if a%con != 0:
                count +=1
            if count >= 2:
                
                flag = False
                break
        if flag and maxi < con:
            maxi = con
    print(maxi)
a, b = map(int, input().split())
sum = 0
for i in range(1,2):
	if a < b:
      sum += b
      b -= 1
    else:
      sum += a
      a -= 1
print(sum)

### FIXED CODE ###

A,B = map(int, input().split())
sum = 0
for i in range(2):
  if A < B:
    sum += B
    B -= 1
  else:
    sum += A
    A -= 1
print(sum)
s = input()
cnt = 0
cntflg = False
endflg = False
for i in s:
        if i == 'Z' and cntflg:
                cnt += 1
                endflg = True
        elif i == 'Z' and endflg:
                cnt += 1
        elif endflg
                break
        elif cntflg:
                cnt += 1
        elif i == 'A' and not(cntflg):
                cnt = 1
                cntflg = True

print(cnt)


### FIXED CODE ###

s = input()
left = 0
right = 0

for idx, val in enumerate(s):
        if val == 'A':
                left = idx
                break

for idx, val in enumerate(reversed(s)):
        if val == 'Z':
                right = idx
                break

print(len(s) - left - right)
num = int(input())
range_arr = range(num)

strs = [[] for i in range_arr]
for i in range_arr:
    strs[i] = input()

def conv(str):
    str_arr = list(str)
    str_arr.sort()
    return ''.join(str_arr)

new_strs = list(map(lambda v: conv(v), strs))
new_strs.sort()
compact_strs = list(set(new_strs))

cnt = 0
for str in compact_strs:
    str_count = new_strs.count(str)
    print(f'str_count:{str_count}')
    if str_count >= 2:
        cnt += int(str_count*(str_count-1)/2)

print(cnt)


### FIXED CODE ###

from collections import Counter

num = int(input())
range_arr = range(num)

strs = [[] for i in range_arr]
for i in range_arr:
    strs[i] = input()

def sort(str):
    str_arr = list(str)
    str_arr.sort()
    return ''.join(str_arr)

new_strs = list(map(lambda v: sort(v), strs))
strs_length = len(new_strs)

sum = 0
counter = Counter()
for tmp_str in new_strs:
    sum += counter[tmp_str]
    counter[tmp_str] += 1

print(sum)
N = int(input())
#N = 6
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

NN = factorization(N)

# N-1について
NN_1 = factorization(N-1)
#print(NN_1)
ans = 0
tmp = 1
for i in NN_1:
    tmp *= i[1]+1
ans += tmp - 1
#print(ans)

#
P = []
IKU = []
PP = []
for i in NN:
    P.append(i[0])
    j = i[1]
    tmp = []
    for k in range(j+1):
        tmp.append(k)
    PP.append(tmp)
    IKU.append(i[1])
L = len(P)
#print('aaa')
for i in itertools.product(*PP):
    tmp = 1
    for j in range(L):
        tmp *= P[j]**i[j]
    K = tmp
    tmp = 1

    if K != 1:
        #print('K',K)
        for j in range(1,41):
            tmp *= K
            if N<tmp:
                break
            #print(tmp)
            if (N-tmp)%(tmp*K)==0:
                ans += 1
                #print('YES',K)
                break
            
#print(NN_1)
#print(NN)
print(ans)


### FIXED CODE ###

N = int(input())
import itertools
#N = 6
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

NN = factorization(N)

# N-1について
NN_1 = factorization(N-1)
#print(NN_1)
ans = 0
tmp = 1
for i in NN_1:
    tmp *= i[1]+1
ans += tmp - 1
#print(ans)

#
P = []
IKU = []
PP = []
for i in NN:
    P.append(i[0])
    j = i[1]
    tmp = []
    for k in range(j+1):
        tmp.append(k)
    PP.append(tmp)
    IKU.append(i[1])
L = len(P)
#print('aaa')
for i in itertools.product(*PP):
    tmp = 1
    for j in range(L):
        tmp *= P[j]**i[j]
    K = tmp
    tmp = 1

    if K != 1:
        #print('K',K)
        for j in range(1,41):
            tmp *= K
            if N<tmp:
                break
            #print(tmp)
            if (N-tmp)%(tmp*K)==0:
                ans += 1
                #print('YES',K)
                break
            
#print(NN_1)
#print(NN)
if N==2:
    print(1)
else:
    print(ans)
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

cnt = 0

for a in A:
    
    if(sum([ta * tb for ta, tb in zip(a, B)]) + C > 0):
        cnt += 1

print(cnt)

### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())
print((H - h) * (W - w))
N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [-1] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0

# =====================first sweep
tmp_zero = 1
tmp_one = 1
for i in range(N):
    if X[-i-1] == '1':
        one_S += tmp_one
        one_S %= for_one
        zero_S += tmp_zero
        zero_S %= for_zero
    tmp_zero *= 2
    tmp_zero %= for_zero
    tmp_one *= 2
    tmp_one %= for_one


# =====================second sweep
tmp_zero = 1
tmp_one = 1
for i in range(N):
    if X[-i-1] == '1':
        numbers[-i - 1] = (one_S - tmp_one) % for_one
    else:
        numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
    tmp_zero *= 2
    tmp_zero %= for_zero
    tmp_one *= 2
    tmp_one %= for_one


def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

print(*counts, sep='\n')

### FIXED CODE ###

N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [0] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0
    # =====================first sweep
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

    # =====================second sweep
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            pass
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

else:
    # =====================first sweep
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            one_S += tmp_one
            one_S %= for_one
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one

    # =====================second sweep
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            numbers[-i - 1] = (one_S - tmp_one) % for_one
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one




def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

print(*counts, sep='\n')
import copy
N, K=list(map(int,input().split()))
A=list(map(int,input().split()))
a=max(A)
l=0
y=copy.copy(a)
while l<=a:
    x=(l+a)//2
    m=sum([A[i]//x for i in range(N)]) # x以下にするための回数
    if m<=K:
        a=x-1
        y=copy.copy(x)
    else:
        l=x+1
print(y)

### FIXED CODE ###

import copy
N, K=list(map(int,input().split()))
A=list(map(int,input().split()))
a=max(A)
l=1
y=copy.copy(a)
a=a-1
while l<=a:
    x=(l+a)//2
    m=0
    for i in range(N):
        if A[i]%x==0:
            m+=A[i]//x-1
        else:
            m+=A[i]//x
    if m<=K:
        a=x-1
        y=copy.copy(x)
    else:
        l=x+1
print(y)
N, Q = map(int,input().split())
S = input()

count_list = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == 'AC':
        count_list[i+1] = count_list[i] + 1
    else:
        count_list[i+1] = count_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(count_list[r-1] - count_list[l-1])

### FIXED CODE ###

b = input()
if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "C":
  print("G")
elif b == "G":
  print("C")
a,b,c,d=map(int, input().split())
 
for i in range( 200 ):
    c=c-b
    if c<=0:
  		print("Yes")
  		break
	a=a-d
  	if a<=0:
  		print("No")
  		break

### FIXED CODE ###


a, b, c, d = map( int, input().split() )
#print( a, b, c, d )
 
for i in range( 200 ):
    c = c - b
    if c <= 0:
        print( "Yes" )
        exit()
 
    a = a - d
    if a <= 0:
        print( "No" )
        exit()
python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    s= str(input())
    ls=len(s)
    cur=ls//2
    i=0
    while True:
        i+=1
        cur-=1
        if s[:cur]==s[cur:ls-i*2]:
            print(ls-i*2)
            break


    
resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    S=list(input())
    while True:
        S.pop(-1)
        l=len(S)
        if S[:l//2]==S[l//2:]:
            print(l)
            break



resolve()
N = int(input())
C = list(map(int,input().split()))

def chose(A):
    s = 0
    t = 0
    for i in range(len(A)):
        t = A.count(i+1) 
        for q in range(t):
            s += q
    print(s)

for i in range(N):
    B = C[:]
    B.pop(i)
    chose(B)

### FIXED CODE ###

N,M = map(int,input().split())
s = t = 0
for i in range(N):
    s += i
for i in range(M):
    t += i
print(s+t)
sentence = raw_input()
ans = []

for i in range(26):
  ans.append(0)

for string in sentence:
  string = string.strip()
  for s in string:
    s = s.lower()
    key = ord(s) - ord('a')
    if 0 <= key <= 25:
      ans[key] += 1

for i in range(len(ans)):
  print('{} : {}".format(chr(ord('a') + i), ans[i]) 

### FIXED CODE ###

import sys
 
text = sys.stdin.readlines()
ans = []
for i in range(26):
    ans.append(0)
for i in text:
    i = i.strip()
    for j in i:
        j = j.lower()
        key = ord(j) - ord("a")
        if 0 <= key <= 25:
            ans[key] += 1
for i in range(len(ans)):
    print "{} : {}".format(chr(ord("a") + i), ans[i])
"""
前処理として、各地点で両替した場合に最終的に残るスヌークを計算しておく。
これは、s地点から各地点までの円での最小コストと t地点から各地点までのスヌークでの最小コストを計算することで可能である。
次に、各地点で両替した場合に残るスヌークを昇順で保持しておく。
これで前処理は完了。

あとは、小さい順に残スヌークを取り出し、その両替地点の番号がi以下であれば、新しい最小値を取り出し、そうでなければ、その値を出力する。
"""
def main():
    import sys
    input = sys.stdin.readline
    import heapq
    n,m,s,t = map(int,input().split())
    def dijkstra(edges,costDic,startPoint):
        que=[(0,startPoint)]
        heapq.heapify(que)
        while que:
            cost,now = heapq.heappop(que)
            if now not in costDic:
                costDic[now] = cost
                for nx,c in edges[now]:
                    if nx not in costDic:
                        heapq.heappush(que,(cost+c,nx))

    yenEdges = [[] for _ in range(n+1)]
    snuukEdges = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        yenEdges[u].append((v,a))
        yenEdges[v].append((u,a))
        snuukEdges[u].append((v,b))
        snuukEdges[v].append((u,b))
    yenDic = {}
    snuukDic = {}

    dijkstra(yenEdges,yenDic,s)
    dijkstra(snuukEdges,snuukDic,t)

    remainingSnuuk = []
    for i in range(1,n+1):
        remainingSnuuk.append((10**15-(yenDic[i]+snuukDic[i])),i)
    remainingSnuuk.sort(key=lambda x: x[0], reverse=True)

    j = 0
    for i in range(n):
        while remainingSnuuk[j][1] <= i:
            j += 1
        print(remainingSnuuk[j][0])
main()

### FIXED CODE ###

import heapq

n,m,s,t = map(int,input().split())
edgesYen = [[]for _ in range(n+1)]
edgesSnuuk = [[]for _ in range(n+1)]

for _ in range(m):
    u,v,a,b = map(int,input().split())
    edgesYen[u].append((v,a))
    edgesYen[v].append((u,a))
    edgesSnuuk[u].append((v,b))
    edgesSnuuk[v].append((u,b))


def dijkstra(edges,costDic,que):
    while que:
        cost,now = heapq.heappop(que)
        if now not in costDic:
            costDic[now] = cost
            for nx,c in edges[now]:
                if nx not in costDic:
                    heapq.heappush(que,(cost+c,nx))
#都市sから各都市に円で行く場合の最小コストを求める。
costYen = {}
que1 = [(0,s)]
heapq.heapify(que1)
dijkstra(edgesYen,costYen,que1)

costSnuuk = {}
que2 = [(0,t)]
heapq.heapify(que2)
dijkstra(edgesSnuuk,costSnuuk,que2)


minimumCosts = []
for i in range(1,n+1):
    cost = costYen[i] + costSnuuk[i]
    minimumCosts.append((cost,i))
heapq.heapify(minimumCosts)

money = 10**15
tmp = heapq.heappop(minimumCosts)
for i in range(n):
    while tmp[1] <= i:
        tmp = heapq.heappop(minimumCosts)
    print(money-tmp[0])