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

n = int(input())
A = []
for i in range(n):
    A.append(int(input()))

A_max = max(A)
for i in range(n):
    if A[i] == A_max:
        print(max(A[0:i] + A[i+1:n]))
    else:
        print(A_max)


### FIXED CODE ###

n = int(input())
A = []
for i in range(n):
    A.append(int(input()))

A_max = max(A)
A_max_2 = sorted(A)[-2]
for i in range(n):
    if A[i] == A_max:
        print(A_max_2)
    else:
        print(A_max)
### BUGGY CODE ###

from heapq import heappush, heappop, heapify

def main():
    N, M = map(int, input().split())
    A_card = [int(x) for x in input().split()]

    change_list = []
    for i in range(M):
        B, C = [int(x) for x in input().split()]
        change_list.append((C, B))

    hq = []
    for i in range(N):
        heappush(hq, (-A_card[i], 1))

    for i in range(M):
        for j in range(change_list[i][1]):
            heappush(hq, (-change_list[i][0], 1))

    result_sum = 0
    for i in range(N):
        tmp = (-1) * heappop(hq)[0]
        result_sum += tmp

    print(result_sum)




if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappush, heappop, heapify

def main():
    N, M = map(int, input().split())
    A_card = [-int(x) for x in input().split()]

    change_list = []
    for i in range(M):
        B, C = [int(x) for x in input().split()]
        change_list.append(((-1) * C, B))

    hq = []
    for i in range(N):
        heappush(hq, (A_card[i], 1))

    for i in range(M):
        heappush(hq, change_list[i])

    result_sum = 0
    count = 0
    while True:
        if count == N:
            break
        tmp = heappop(hq)
        if count + tmp[1] <= N:
            result_sum += (tmp[0] * tmp[1])
            count += tmp[1]
        else:
            result_sum += (tmp[0] * (N - count))
            break

    print(result_sum * (-1))

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

n=int(input())
a = 1
for i in map(int,input().split()):
	a *= i
 
if a>10e17:
	print(-1)
else:
	print(a)

### FIXED CODE ###

import sys

n=int(input())
l=list(map(int,input().split()))

if 0 in l:
	print(0)
	sys.exit()

flg=False
a = 1
for i in l:
	a *= i
	if a>10e17:
		flg=True
		break
 
if flg:
	print(-1)
else:
	print(a)
### BUGGY CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#V, E, r = map(int, input().split())
#INF = V * 10001
#A = [int(i) for i in input().split()]


N = int(input())
A = [int(i) for i in input().split()]
dp = [0]*(N+1)
ans = 0
a = [0]*N
minus = 0

for i in range(N):
  a[i] = A.count(A[i])
  if(a[i]<2):
    dp[A[i]] = 0
  else:
    dp[A[i]] = combinations_count(a[i], 2)

ans = sum(dp)

#print(dp)
for i in range(N):
  temp = dp[A[i]]
  if(a[i]==2):
    minus = temp-1
  elif(a[i]<2):
    minus = temp
  else:
    minus = combinations_count(a[i]-1, 2)
  print(int(ans-(temp-minus)))

#print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#V, E, r = map(int, input().split())
#INF = V * 10001
#A = [int(i) for i in input().split()]


N = int(input())
A = [int(i) for i in input().split()]
dp = [0]*(N+1)
ans = 0
cnt = 0
tle = 0

As = list(set(A))
c = Counter(A)

for i in As:
  cnt = c[i]
  if(cnt<2):
    dp[i] = 0
  else:
    dp[i] = combinations_count(cnt, 2)

tle = sum(dp)

#print(dp)
for i in range(N):
  ans = tle - (c[A[i]]-1)
  if(ans < 0):
    ans = 0
  print(int(ans))

#print(ans)
### BUGGY CODE ###

x,y,z,K=map(int,input().split())
listsa=list(map(int,input().split()))#長さはｘ
listsb=list(map(int,input().split()))#長さはy
listsc=list(map(int,input().split()))#長さはz
if x*y>3000:
    suballlist=[]
    for i in listsa:
        for j in listsb:
            suballlist.append(i+j)
    suballlist=sorted(suballlist,reverse=True)
    uselist=suballlist[:3000]
    alllist=[]
    for i in uselist:
        for j in listsc:
            alllist.append(i+j)
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])
    
elif x*y<=3000:
    alllist=[]
    for i in listsa:
        for j in listsb:
            for k in listsc:
                alllist.append(i+j+k)
                
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
x,y,z,K=map(int,input().split())
listsa=list(map(int,input().split()))#長さはｘ
listsb=list(map(int,input().split()))#長さはy
listsc=list(map(int,input().split()))#長さはz
if x*y>3000:
    suballlist=[]
    for i in listsa:
        for j in listsb:
            suballlist.append(i+j)
    suballlist=sorted(suballlist,reverse=True)
    uselist=suballlist[:3000]
    alllist=[]
    
    for i in uselist:
        for j in listsc:
            alllist.append(i+j)
            
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])
    
elif x*y<=3000:
    alllist=[]
    for i in listsa:
        for j in listsb:
            for k in listsc:
                alllist.append(i+j+k)
                
    alllist=sorted(alllist,reverse=True)
    for i in range(K):
        print(alllist[i])
### BUGGY CODE ###

def main():
    N = int(input())
    L = list(map(int,input().split()))
    count = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            for k in range(j+1,N):
            
                if (L[i]<L[j]+L[k]) and (L[j] < L[i]+L[k]) and (L[k] < L[j]+L[i]):
                    count += 1
    print(count)
main()

### FIXED CODE ###

import bisect
def main():
    N = int(input())
    L = list(map(int,input().split()))
    L.sort()
    
    count = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            c = bisect.bisect_left(L,L[i]+L[j])
            
            count += max(0,c-1 - j)
    
    print(count)
main()
### BUGGY CODE ###

# coding: utf-8
# このファイルはutf-8で書かれているため、日本語を書く場合は上の記述が必要


count_num = int( input())


text = input()


num_data = text.split(' ')

ans = 1
for i in num_data:
        ans = ans * int(i)

if ans > 1000000000000000000:
        ans = -1

print(ans)

### FIXED CODE ###

# coding: utf-8
# このファイルはutf-8で書かれているため、日本語を書く場合は上の記述が必要

count_num = int( input())
text = input()

num_data = text.split(' ')

ans = 1
for i in num_data:
        if i == '0':
                ans = 0
                break

if ans == 1:
        for i in num_data:
                ans = ans * int(i)
                if ans > 1000000000000000000:
                        ans = -1
                        break

print(ans)
### BUGGY CODE ###

N = int(input())
nu = [int(x) for x in input().split()]
r2 = {}

for i in nu:
  r2[i] = nu.index(i)
#print(r2)

j2 = []
for i in range(len(r2)):
  j2.append(r2[i+1]+1)
#print(j2)

answ = ""
for i in j2:
  answ = answ + str(i) + " "
print(answ)

### FIXED CODE ###

n1 = int(input())
l1 = [int(x) for x in input().split()]
l2 = [""] * n1

for i, v in enumerate(l1):
  l2[v -1] = i + 1

l2 = map(str,l2)
ans = " ".join(l2)
print(ans)
### BUGGY CODE ###

K, S = map(int, raw_input().split())
cnt = 0
for i in range(0, K+1):
	if S - i <= 2*K:
		for j in range(0, K+1):
			if S - i - j <= K:
				for k in range(0, K+1):
					if S - i - j - k == 0:
						cnt += 1
						break

print cnt

### FIXED CODE ###

K, S = map(int, raw_input().split())
cnt = 0
for i in range(0, K+1):
	if S - i <= 2*K:
		for j in range(0, K+1):
			if 0 <= S - i - j and S - i - j <= K:
				cnt+=1
print cnt
### BUGGY CODE ###

A, B, K = input().split(' ')
A = int(A)
B = int(B)
K = int(K)
N = []
for i in range(A, B+1):
  if i < A + K:
    N.append(i)
  elif i > B-K:
    N.append(i)
for i in range(len(N)):
  print(N[i])

### FIXED CODE ###

A, B, K = input().split(' ')
A = int(A)
B = int(B)
K = int(K)
N = []
if B-A>K:
  for i in range(A, A+K):
    print(i)
    N.append(i)
  for i in range(B-K+1, B+1):
    if not i in N:
      print(i)

else:
  for i in range(A, B+1):
    if i < A + K:
      print(i)
    elif i > B-K:
      print(i)
### BUGGY CODE ###

N=int(input())
S=list(str(input()))
count=0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if j-i!=k-j and S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=list(str(input()))
r=S.count('R')
g=S.count('G')
b=S.count('B')
count=0

for i in range(int((N-3)/2)+1):
    for k in range(N-i*2-3+1):
        if S[k]!=S[k+i+1] and S[k]!=S[k+2*i+2] and S[k+i+1]!=S[k+2*i+2]:
            count+=1
print(r*g*b-count)
### BUGGY CODE ###

""" AtCoder """

S = input()
T = input()

for i in range(len(S)):
    index = i
    tmp = T[i]
    while True:
        index = S.find(S[i], index + 1)
        if index == -1:
            break

        if tmp != T[index]:
            print("No")
            exit()

for i in range(len(T)):
    index = i
    tmp = S[i]
    while True:
        index = T.find(T[i], index + 1)
        if index == -1:
            break
        if tmp != S[index]:
            print("No")
            exit()

print("Yes")


### FIXED CODE ###

""" AtCoder """
import collections

S = input()
T = input()

s = {}
t = {}

for i in range(len(S)):
    if S[i] in s and s[S[i]] != T[i] or T[i] in t and t[T[i]] != S[i]:
        print("No")
        exit()
    s[S[i]] = T[i]
    t[T[i]] = S[i]

print("Yes")
### BUGGY CODE ###

n,m = map(int,input().split())
li = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    li[a][b] = 1
    li[b][a] = 1

ans = False
for i in range(1,n-1):
    if li[0][i] and li[i][n-1]:
        ans = True
        break

if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
li1 = [0 for _ in range(n)]
li2 = [0 for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if a==0:
        li1[b] = 1
    elif b==n-1:
        li2[a] = 1

ans = False
for i in range(1,n-1):
    if li1[i] and li2[i]:
        ans = True
        break

if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    
    idx = 0
    ans = 0
    for i in range(len(A)):
        if idx + 1 > len(A) - 1 :
            break

        m = ""
        if A[idx] < A[idx + 1]:
            m = "+"
        elif A[idx] > A[idx + 1]:
            m = "-"
        else:
            find = False
            for j in range(idx, len(A)-1):
                if A[j] < A[j + 1]:
                    m = "+"
                    find = True
                    break
                elif A[j] > A[j + 1]:
                    m = "-"
                    find = True
                    break
            if find == False:
                print(ans + 1)
                exit()

        for j in range(idx, len(A) - 1):
            if m == "+":
                if A[j] <= A[j + 1]:
                    pass
                else:
                    idx = j + 1
                    ans += 1
                    break
            elif m == "-":
                if A[j] >= A[j + 1]:
                    pass
                else:
                    idx = j + 1
                    ans += 1
                    break

    print(ans + 1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    idx = 0
    ans = 0
    for i in range(len(A)):
        if idx + 1 > len(A) - 1 :
            break

        m = ""
        if A[idx] < A[idx + 1]:
            m = "+"
        elif A[idx] > A[idx + 1]:
            m = "-"
        else:
            find = False
            for j in range(idx, len(A)-1):
                if A[j] < A[j + 1]:
                    m = "+"
                    find = True
                    idx = j
                    break
                elif A[j] > A[j + 1]:
                    m = "-"
                    find = True
                    idx = j
                    break
            if find == False:
                print(ans + 1)
                exit()

        for j in range(idx, len(A) - 1):
            if m == "+":
                if A[j] <= A[j + 1]:
                    idx = j + 1
                else:
                    idx = j + 1
                    ans += 1
                    break
            elif m == "-":
                if A[j] >= A[j + 1]:
                    idx = j + 1
                else:
                    idx = j + 1
                    ans += 1
                    break

    print(ans + 1)

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

N = int(input())
P = tuple(map(int, input().split()))

m = 0

for i in range(0, N, 1):
    if P[i] <= min(P[:i+1]):
        m += 1

print(m)

### FIXED CODE ###

N = int(input())
P = tuple(map(int, input().split()))

pmin = P[0]

m = 1

for i in range(1, N, 1):
    if P[i] < pmin:
        pmin = P[i]
        m += 1

print(m)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = [0.0] * 10000

rmax = -1
pos = -1
for i in range(n-k+1):
    _t = sum(p[i: i+k])
    if pos < _t:
        pos = _t
        rmax = i

ans = 0.0
p = p[rmax: rmax+k]
p = sorted(p, reverse=True)

for i in range(k):
    if tmp[p[i]] == 0:
        t = 0
        for j in range(1, p[i]+1):
            t += j
            tmp[j] = t / j
        ans += tmp[p[i]]
    else:
        ans += tmp[p[i]]

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s = [0] * (n+1)

for i in range(0, n):
    s[i+1] = s[i] + p[i]

s_max = -1
pos = 0
for i in range(n-k+1):
    ss = s[i+k] - s[i]
    if ss > s_max:
        s_max = ss
        pos = i

ans = 0.0
for i in range(pos, pos+k):
    ans += (p[i]+1) / 2

print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]
dp = [0 for _ in range(0,N+1)]
dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0
for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if (i-1) not in arr: dp[i] += dp[i-1]
    if (i-2) not in arr: dp[i] += dp[i-2]
print(dp[N] % (10**9 + 7))

### FIXED CODE ###

N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0,N+1)]
for x in arr:
    stairs[x] = False

dp = [0 for _ in range(0,N+1)]

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)
### BUGGY CODE ###

# 入力
N=int(input())

a=1
while True:
  b=a*a
  
  if N==b:
    print(b)
    break
  
  elif N<b:
    print((a-1)*(a-1))
    break

### FIXED CODE ###

import math;a=int(math.sqrt(int(input()))//1);print(a*a)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*N

for i in range(1, N):
  dp[i] = dp[i-1]+abs(h[i]-h[i-1])
  L = min(K, i)
  for j in range(2, L+1):
    dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
c = [0]*N
for i in range(1, N):
    c[i] = min([c[j] + abs(h[i]-h[j]) for j in range(max(0, i-K), i)])
print(c[N-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

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

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

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

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 5)

n, m, p = map(int, input().split())
abc = []
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])

d = [[float('inf') for _ in range(n)] for _ in range(n*2 + 1)]

d[0][0] = 0

for i in range(1, n):
    for a, b, c in abc:
        d[i][b] = min(d[i][b], d[i-1][b], d[i-1][a] + c)

for a, b, c in abc:
    if d[n-1][b] > d[n-1][a] + c:
        d[n-1][b] = - float('inf')

for i in range(n, 2*n+1):
    for a, b, c in abc:
        d[i][b] = min(d[i][b], d[i-1][b], d[i-1][a] + c)

if d[n*2][n-1] == - float('inf'):
    print(-1)
else:
    print(max(- d[n*2][n-1], 0))


### FIXED CODE ###

n, m, p = map(int, input().split())
abc = []
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])

d = [float('inf')] * n
d[0] = 0

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

for a, b, c in abc:
    if d[b] > d[a] + c:
        d[b] = - float('inf')

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

if d[n-1] == - float('inf'):
    print(-1)
else:
    print(max(0, - d[n-1]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
L = [0] * (N + 1)

for i in A:
    L[i] += 1

for i in range(1,len(L)):
    print(L[i])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""

R,G,B,N = tuple(map(int,input().split()))
c = 0
rmax = N//R

for i in range(rmax+1):
    gmax = (N-R*i)//G
    for j in range(gmax+1):
        bmax = (N-R*i-G*j)//B
        for k in range(bmax+1):
            if R*i+G*j+B*k == N:
                c += 1

print(c)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""

R,G,B,N = tuple(map(int,input().split()))
L = [R,G,B]
L.sort(reverse=True)
c = 0
rmax = N//L[0]

for i in range(rmax+1):
    Nc = N
    Nc -= i*L[0]
    if Nc%L[2] == 0:
            c += 1
    while True:
        Nc -= L[1]
        if Nc < 0:
            break
        if Nc%L[2] == 0:
            c += 1

print(c)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict, deque
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = deque([[0, min(S, A)]])
    while len(s) > 0:
        tu, i = s.popleft()
        for vab in uvab[tu]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[tu, i] + b:
                dp[v, i-a] = dp[tu, i] + b
                s.append([v, i-a])
            elif i == A and dp[v, i] > dp[tu, i] + b:
                dp[v, i] = dp[tu, i] + b
                s.append([v, i])
        c, d = cd[tu]
        t = i
        while t < A:
            nt = min(t+c, A)
            if dp[tu, nt] > dp[tu, t] + d:
                dp[tu, nt] = dp[tu, t] + d
                s.append([tu, nt])
            t = nt
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()
### BUGGY CODE ###

N, Y = map(int,input().split())
for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            if i + j + k == N and 10000 * i + 5000 * j + 1000 * k == Y:
                print(i,j,k)
                exit()
print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int,input().split())
for i in range(N+1):
    for j in range(N+1-i):
        if  10000 * (N - i - j)+ 5000 * j + 1000 * i == Y:
            print(N - i - j,j,i)
            exit()
print("-1 -1 -1")