Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]

    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.6:
            print((N*(N-1))//2)
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
A2 = [a for a in A if A.count(a)>=2]
A2.sort()
print(A2[-1]*A2[-4] if len(A2)>=4 else 0)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = Counter(list(map(int, input().split())))
E = [0, 0]
for k, v in A.items():
    if v>=2:
        E.append(k)
    if v>=4:
        E.append(k)
E.sort()
print(E[-1]*E[-2])
### BUGGY CODE ###

n = int(input())
perputation = list(map(int, input().split()))
cnt = 1

if n == 1:
    print("1")
else:
    for i in range(1, n):
        if min(perputation[:i]) >= perputation[i]:
            cnt += 1
    print(cnt)

### FIXED CODE ###

n = int(input())
perputation = list(map(int, input().split()))
cnt = 1
last_min = perputation[0]

if n == 1:
    print("1")
else:
    for i in range(1, n):
        if last_min >= perputation[i]:
            cnt += 1
            last_min = perputation[i]
    print(cnt)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
n,Q = [int(i) for i in input().split()]
from heapq import  *

stx=[]
for j in range(n):
    a = [int(i) for i in input().split()]
    stx.append([a[1]-a[2],0,a[2]])
    stx.append([a[0]-a[2],1,a[2]])
q = [int(input()) for i in range(Q)]
stx.sort()
s=set()

#print(stx)
pt=0
for i in q:
    while pt < 2*n and i >= stx[pt][0]:
        st,lr,x=stx[pt]
        if lr == 1:
            s.add(x)
        else:
            s.remove(x)
        pt+=1
#    print(s)
    if s:
        print(min(s))
    else:
        print(-1)
    











### FIXED CODE ###

import sys
from heapq import *
input = sys.stdin.readline

n,Q = [int(i) for i in input().split()]

stx=[[0]*3 for _ in range(n)]
for j in range(n):
    a = [int(i) for i in input().split()]
    stx[j]=[a[0]-a[2],a[1]-a[2],a[2]]
q = [int(input()) for i in range(Q)]
stx.sort()

xt=[]
pt=0
for d in q:
    while pt < n and stx[pt][0] <= d:
        heappush(xt,(stx[pt][2],stx[pt][1]))
        pt+=1
    while xt and xt[0][1] <= d:
        heappop(xt)
    if xt:
        print(xt[0][0])
    else:
        print(-1)
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    def kanashimi(n):
        soinsu = set()
        divider = 1
        while n != 1:
            divider += 1
            while n % divider == 0:
                n //= divider
                soinsu.add(divider)

        return soinsu

    a_kanashimi = kanashimi(a)
    b_kanashimi = kanashimi(b)

    ans = a_kanashimi & b_kanashimi

    print(len(ans) + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    g = fractions.gcd(a, b)

    def search(n):
        i = 2
        so = []
        while not(n == 1 or i * i > n):
            while n % i == 0:
                n //= i
                so.append(i)
            i += 1
        if n != 1:
            so.append(n)

        return so

    ans = set(search(g))
    print(len(ans) + 1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())
### BUGGY CODE ###

from collections import deque

n = int(input())
dict = deque()
for i in range(n):
    order = input().split()
    if order[0] == "insert":
        dict.append(order[1])
    else:
        if order[1] in dict:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

from collections import deque

n = int(input())
dict = {}
for i in range(n):
    order = input().split()
    if order[0] == "insert":
        dict[order[1]] = i
    else:
        if order[1] in dict:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

from itertools import combinations
from collections import defaultdict
N,X,Y= map(int,input().split())

ans = defaultdict(int)
for i, j in combinations(range(1,N+1),2):
    d = min(abs(i-j),abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    ans[d] += 1

for i in range(1,N):
    print(ans[i])





### FIXED CODE ###

from itertools import combinations
from collections import defaultdict
N,X,Y= map(int,input().split())

ans = defaultdict(int)
for i, j in combinations(range(1,N+1),2):
    d = min(abs(i-j),abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
    ans[d] += 1

for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
B = [0] * M
C = [0] * M
A.sort()
#print(A)
for m in range(M):
    b, c = map(int, input().split())
    index = bisect.bisect_right(A, c)
    #print(f'index >> {index}')
    if index > 0:
        if index - b < 0:
            A[:index] = [c] * index
        else:
            A[: index - b] = A[b: index]
            A[index - b: index] = [c] * b
    #print(A)

print(sum(A))

### FIXED CODE ###

import sys
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort()
#print(A)
BC = [0] * M
for m in range(M):
    BC[m] = list(map(int, input().split()))
BC.sort(key=lambda x: x[1], reverse=True)
#print(BC)
c = 0
for m in range(M):
    for t in range(BC[m][0]):
        if BC[m][1] > A[c]:
            A[c] = BC[m][1]
        c += 1
        if c == N:
            print(sum(A))
            sys.exit()
print(sum(A))
### BUGGY CODE ###

import fractions
import itertools

k=int(input())
tot=0
for l,m,n in itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)):
    ans=l
    ans=fractions.gcd(ans,m)
    ans=fractions.gcd(ans,n)
    tot+=ans
print(tot)

### FIXED CODE ###

import math
k= int(input())
tot= 0
for i in range(1, k+1):
    for j in range(1, k+1):
        m = math.gcd(i,j)
        for n in range(1, k+1):
            l = math.gcd(m,n)
            tot += l
print(tot)
### BUGGY CODE ###

import math


def main():
    a,b,n = map(int,input().split())
    m = math.floor(a * 0 /b) - a * math.floor(0/b)
    for i in range(1,n+1):
        if m < math.floor(a * i / b) - a * math.floor(i/b):

            m = math.floor(a * i / b) - a * math.floor(i/b)
    print(m)
if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    a,b,n = map(int,input().split())
    # m = math.floor(a * 0 /b) - a * math.floor(0/b)
    # for i in range(1,min(b-1,n)+1):
    #     if m < math.floor(a * i / b) - a * math.floor(i/b):
    #         m = math.floor(a * i / b) - a * math.floor(i/b)
    i = min(b-1,n)
    m = a*i//b - a*(i//b)
    
    print(m)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys


def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i


def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
rli = sorted((r << 40) + (l << 20) + i for i, (l, r) in enumerate(zip(mp, mp)))
mask = (1 << 20) - 1

bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for k in rli:
    r = k >> 40
    l = (k >> 20) & mask
    i = k & mask
    while p < r:
        c = ccc[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1

    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)

print('\n'.join(map(str, ans)))


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2:2 + n]
    lll = inp[2 + n::2] - 1
    rrr = inp[3 + n::2] - 1

    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(q):
        segments.append((rrr[i], 1, lll[i], i))

    segments.sort()
    bit = np.zeros(n + 2, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, n + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import math

def Sieve_of_Eratosthenes(n):
    if n < 2:
        raise ValueError('n is more than 2.')
    prime = []
    limit = math.sqrt(n)
    can = [i for i in range(2, n+1)]
    while True:
        p = can[0]
        if limit <= p:
            return prime + can
        prime.append(p)
        can = [x for x in can if x%p != 0]

q = int(input())
l_r = []
for _ in range(q):
    l, r = map(int, input().split())
    l_r.append((l,r))

can = Sieve_of_Eratosthenes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)

    


### FIXED CODE ###

import math

def Sieve_of_Eratosthenes(n):
    if n < 2:
        raise ValueError('n is more than 2.')
    prime = []
    limit = math.sqrt(n)
    can = [i for i in range(2, n+1)]
    while True:
        p = can[0]
        if limit <= p:
            return prime + can
        prime.append(p)
        can = [x for x in can if x%p != 0]

q = int(input())
l_r = []
for _ in range(q):
    l, r = map(int, input().split())
    l_r.append((l,r))

can = Sieve_of_Eratosthenes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
n = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-(x+y)
        if z <= k and z >= 0 and x+y+z==s:
            n += 1
print(n)
                

### FIXED CODE ###

k,s = map(int,input().split())
n = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-(x+y)
        if z <= k and z >= 0 and x+y+z==s:
            n += 1
print(n)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(knapsack_dp[N-1][W])

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

    knapsack_dp = [[0 for _ in range(W+1)] for _ in range(N)]

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

    print(knapsack_dp[N-1][W])

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = list(range(1, N+1))

for i in range(0, N):
    for j in range(N-1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            ans[j], ans[j-1] = ans[j-1], ans[j]

print(*ans, sep=" ")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = list(range( N))

for i in range(N):
    ans[A[i]-1] = i+1

print(*ans, sep=" ")
### BUGGY CODE ###

import collections
import math

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)

cmb = 0
for x in c.values():
    if x >= 2:
        cmb += math.factorial(x) // (math.factorial(2) * math.factorial(x - 2))  

for z in a:
    y = c.get(z)
    ans = cmb
    if y == 2:
        ans -= 1
    elif y >= 3:
        ans -= (math.factorial(y) // (math.factorial(2) * math.factorial(y - 2))) - (math.factorial(y - 1) // (math.factorial(2) * math.factorial(y - 3)))
    print(ans)

### FIXED CODE ###

import collections
import math

def cmb_factorial(s):
    return math.factorial(s) // (math.factorial(2) * math.factorial(s - 2))

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
f = {}

cmb = 0
for x in c.values():
    f[1] = 0
    f[2] = 1
    if x >= 3:
        f[x] = cmb_factorial(x)
        if x - 1 not in f:
            f[x - 1] = cmb_factorial(x - 1)
    cmb += f.get(x)

for z in a:
    y = c.get(z)
    ans = cmb
    if y >= 2:
        ans = cmb - f.get(y) + f.get(y - 1)
    print(ans)
### BUGGY CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)
    for u, a, b in graph[v]:
        if s - a < 0:
            continue
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    heapq.heappush(heap, (d + dd, v, s + c))

ans = [INF] * (N + 1)
ans[1] = 0
for (v, s), d in dp.items():
    ans[v] = min(ans[v], d)
print(*ans[2:], sep='\n')


### FIXED CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')