CodeEff/ECCO huggingface dataset:
# Original solution
N = int(eval(input()))
l = list(map(int,input().split()))
d = l.copy()

count = 0
i = 0
while len(d) != 0:
    if count == 0:
        a = 0
        count += 1
        for j in range(N-count):
            target = d[i] ^ d[j]
            if target in d :
                a += 1
                i = j
            if a == 1:
                break
        if a >= 1 :
            i2 = target
            mae =d[i]
            d.pop(i)
        else:
            print('No')
            break
    
    elif 1 <= count <= N-3:
        a = 0
        count += 1
        for j in range(N-count):
            if target == mae ^ d[j] :
                a += 1
                i = j
            if a == 1:
                break
        if a >= 1 :
            mae =d[i]
            d.pop(i)
        else:
            print('No')
            break
    
    elif count == N-2:
        a = 0
        count += 1
        if mae == target ^ l[0] :
            pass
        else:
            print('No')
            break    

    else:
        if l[0] == i2  ^   mae :
            print('Yes')
            break
        else:
            print('No')
            break 

# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))
a_unique = list(set(a))
a_unique.sort()

if len(a_unique) == 1 and a[0] == 0:
    ans = 'Yes'
elif len(a) % 3 == 0 :
    if len(a_unique) == 3:
        if bin(a_unique[0]) == bin(a_unique[1] ^ a_unique[2]) and bin(a_unique[1]) == bin(a_unique[0] ^ a_unique[2]) and bin(a_unique[2]) == bin(a_unique[1] ^ a_unique[0]) and a.count(a_unique[1]) == N//3 and a.count(a_unique[0]) == N//3 :
            ans = 'Yes'
        else:
            ans = 'No'
    elif len(a_unique) == 2:
        if a_unique[0] == 0 and a.count(a_unique[1]) == N//3 * 2:
            ans = 'Yes'
        else:
            ans = 'No'
    else:
        ans = 'No'
else:
    ans = 'No'

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().strip().split()))

f = []

for i in range(1,n):
    for j in range(1,n):
        if not i == j:
            if a[0] ^ a[j] == a[i]:
                b = [-1] * n
                b[0] = a[0]
                b[1] = a[i]
                b[2] = a[j]
                f.append(b)

for i in range(3,n):
    for j in range(len(f)):
        s = set(a)
        for k in range(i):
            s.discard(f[j][k])
        s = list(s)

        count = 0
        for k in range(n-i):
            if f[j][i-2] ^ s[k] == f[j][i-1]:
                if count <= 0:
                    f[j][i] = s[k]
                    count += 1
                else:
                    b = f[j]
                    b[i] = s[k]
                    f.append(b)

ans_flag = False
for i in range(len(f)):
    if f[i][n-2] ^ f[i][0] == f[i][n-1]:
        ans_flag = True
        break

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


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().strip().split()))

s = []

for i in range(n):
    for j in range(n):
        if not i == j:
            s.append(a[i] ^ a[j])

#print(a)
#print(s)

ans_flag = True
for i in range(n):
    sub_flag = False
    for j in range(len(s)):
        if a[i] == s[j]:
            s[j] = -1
            sub_flag = True
            break
    if sub_flag == False:
        ans_flag = False
        break

#print(a)
#print(s)

if ans_flag:
    print('Yes')
else:
    print('No')
# Original solution
from sys import stdin
from collections import defaultdict
def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    d = defaultdict(int)
    for x in a:
        d[x] += 1
    s = list(d.keys())
    if len(s) == 1:
        print('Yes' if s[0] == 0 else 'No')
    elif len(s) == 2:
        print('Yes' if (0 in s and (d[s[0]] == d[s[1]] or n % 3 == 0 and d[0] == n / 3)) else 'No')
    elif len(s) == 3:
        print('Yes' if (s[0] ^ s[1] ^ s[2] == 0 and d[s[0]] == d[s[1]] == d[s[2]]) else 'No')
    else:
        print('No')
main()


# Optimized solution
from sys import stdin
from collections import defaultdict
def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    d = defaultdict(int)
    for x in a:
        d[x] += 1
    s = list(d.keys())
    if len(s) == 1:
        print('Yes' if s[0] == 0 else 'No')
    elif len(s) == 2:
        print('Yes' if (0 in s and n % 3 == 0 and d[0] == n / 3) else 'No')
    elif len(s) == 3:
        print('Yes' if (s[0] ^ s[1] ^ s[2] == 0 and d[s[0]] == d[s[1]] == d[s[2]]) else 'No')
    else:
        print('No')
main()
# Original solution
import itertools
n = int(eval(input()))
a = list(map(int, input().split()))

ab = list(itertools.permutations(a[1:]))
abc = [[0]*(n+1) for _ in range(len(ab))]

ans = 'No'

for i in range(len(ab)):
  abc[i] = list(ab[i])
  abc[i].append(a[0])
  abc[i].append(a[1])

  for j in range(1,n):
    if bin(abc[i][j-1]^abc[i][j+1]) != bin(abc[i][j]):
      break
    if j == n-1:
      ans = 'Yes'

    
print(ans)

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

n = int(eval(input()))
a = list( map(int, input().split()))

sa = set(a)
sa = list(sa)

if len(sa)>3:
    print('No')
    exit()

if len(sa)==3:
    aa = sa[0]
    bb = sa[1]
    cc = sa[2]
    if a.count(aa) != n/3 or a.count(bb) != n/3 or a.count(cc) != n/3:
        print('No')
        exit()
    if aa^bb^cc!=0:
        print('No')
        exit()

if len(sa)==2:
    aa = sa[0]
    bb = sa[1]
    if bb != 0 and aa != 0:
        print('No')
        exit()
    else:
        if aa==0:
            aa = bb
    if a.count(0) != n/3 or a.count(aa)!=n/3*2:
        print('No')
        exit()

if len(sa)==1:
    aa = sa[0]
    if aa != 0:
        print('No')
        exit()

print('Yes')
# Original solution
n=int(eval(input()))
al=list(map(int,input().split()))
t=0
for i in range(n):
    t^=al[i]
if t==0:
    print('Yes')
else:
    print('No')

# Optimized solution
n=int(eval(input()))
al=list(map(int,input().split()))
t=0
for a in al:
    t^=a
print(('Yes' if t==0 else 'No'))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))

a = list(set(A))

ans = "No"

if len(a) == 1:
    if a == [0]:
        ans = "Yes"
elif len(a) == 2:
    if N % 3 == 0 and A.count(0) == N//3:
        ans = "Yes"
elif len(a) == 3:
    if a[0] ^ a[1] ^ a[2] == 0 and N % 3 == 0 and (A.count(a[0]),A.count(a[1]),A.count(a[2])) == (N//3,N//3,N//3):
        ans = "Yes"

print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))

a = list(set(A))

ans = "No"

if len(a) == 1:
    if a == [0]:
        ans = "Yes"
elif len(a) == 2:
    if N % 3 == 0 and A.count(0) == N//3:
        ans = "Yes"
elif len(a) == 3:
    if a[0] ^ a[1] ^ a[2] == 0 and N % 3 == 0 and (A.count(a[0]),A.count(a[1])) == (N//3,N//3):
        ans = "Yes"

print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))

a = list(set(A))

ans = "No"

if a == [0]:
    ans = "Yes"
elif len(a) == 2:
    if N % 3 == 0 and A.count(0) == N//3:
        ans = "Yes"
elif len(a) == 3:
    if a[0] ^ a[1] == a[2] and N % 3 == 0 and A.count(a[0]) == A.count(a[1]) == N//3:
        ans = "Yes"

print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))

a = list(set(A))

ans = "No"

if a == [0]:
    ans = "Yes"
elif len(a) == 2:
    if (a[0] == 0 or a[1] == 0) and N % 3 == 0 and A.count(0) == N//3:
        ans = "Yes"
elif len(a) == 3:
    if a[0] ^ a[1] == a[2] and N % 3 == 0 and A.count(a[0]) == A.count(a[1]) == N//3:
        ans = "Yes"

print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

def XOR(x, y):
  u, i = 0, 0
  while x != 0 or y != 0:
    u += ((x + y) % 2) * (2 ** i)
    x //= 2
    y //= 2
    i += 1
  return u

Q = []
for i in range(1, len(A)):
  M = XOR(A[0], A[i])
  L = [A[0], A[i]]
  for j in range(len(A)-2):
    L.append(XOR(L[j], L[j+1]))
  Q.append(L)

B = A[:]
k = 0
for s in range(len(Q)):
  for l in range(len(Q[s])):
    for g in range(len(A)):
      if A[g] == Q[s][l]:
        B[g] = Q[s][l]
  if B == Q[s]:
    k += 1
    
if k != 0:
  print('Yes')
else:
  print('No')

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
def xored(a, b):
  y = 0
  base = 1
  while a != 0 or b != 0:
    y += ((a + b) % 2) * base
    base *= 2
    a //= 2
    b //= 2
  return y

if max(A) == 0:
  print("Yes")
else:
  if N % 3 != 0:
    print("No")
  else:
    D = {}
    for i in A:
      if i in D:
        D[i] += 1
      else:
        D[i] = 1
    if len(D) > 3:
      print("No")
    else:
      if len(D) == 3 and min(D[i] for i in D) == max(D[i] for i in D):
        L = [i for i in D]
        if xored(L[0], L[1]) == L[2]:
          print("Yes")
        else:
          print("No")
      elif len(D) == 2:
        if 0 not in D:
          print("No")
        else:
          if D[0] >= N // 3:
            print("Yes")
          else:
            print("No")
      else:
        print("No")
# Original solution
from heapq import heappop, heappush

n,m,s = list(map(int,input().split()))
e = [[] for _ in range(n)]
for i in range(m):
  u,v,a,b = list(map(int,input().split()))
  u -= 1
  v -= 1
  e[u].append((v,a,b))
  e[v].append((u,a,b))
c = []
d = []
for i in range(n):
  x,y = list(map(int,input().split()))
  c.append(x)
  d.append(y)

INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

def newv(v,s):
  return v*2500+s

s = min(s,2499)
e2 = [[] for _ in range(n*2500)]
for u in range(n):
  for j in range(2500):
    #if j+c[u] < 2500:
    #  e2[newv(u,j)].append((newv(u,j+c[u]),d[u]))
    e2[newv(u,j)].append((newv(u,min(j+c[u],2499)),d[u]))
    for v,a,b in e[u]:
      if j >= a:
        e2[newv(u,j)].append((newv(v,j-a),b))

l = dijkstra(newv(0,s),n*2500,e2)
for i in range(1,n):
  ans = INF
  for j in range(2500):
    ans = min(l[newv(i,j)],ans)
  print(ans)


# Optimized solution
from heapq import heappop, heappush

n,m,s = list(map(int,input().split()))
e = [[] for _ in range(n)]
for i in range(m):
  u,v,a,b = list(map(int,input().split()))
  u -= 1
  v -= 1
  e[u].append((v,a,b))
  e[v].append((u,a,b))
c = []
d = []
for i in range(n):
  x,y = list(map(int,input().split()))
  c.append(x)
  d.append(y)

INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

def newv(v,s):
  return v*2500+s

s = min(s,2499)
e2 = [[] for _ in range(n*2500)]
for u in range(n):
  for j in range(2500):
    if j+c[u] < 2500:
      e2[newv(u,j)].append((newv(u,j+c[u]),d[u]))
    #e2[newv(u,j)].append((newv(u,min(j+c[u],2499)),d[u]))
    for v,a,b in e[u]:
      if j >= a:
        e2[newv(u,j)].append((newv(v,j-a),b))

l = dijkstra(newv(0,s),n*2500,e2)
for i in range(1,n):
  ans = INF
  for j in range(2500):
    ans = min(l[newv(i,j)],ans)
  print(ans)
# Original solution
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

N,m,s=list(map(int,input().split()))
L=[list(map(int,input().split())) for i in range(m)]
L2=[list(map(int,input().split())) for i in range(N)]
n=N*(50*(N-1)+1)
edge=[[] for i in range(n)]
for i in range(m):
  for j in range(50*(N-1)+1):
    if j>=L[i][2]:
      edge[L[i][0]-1+N*j].append([L[i][3],L[i][1]-1+N*(j-L[i][2])])
      edge[L[i][1]-1+N*j].append([L[i][3],L[i][0]-1+N*(j-L[i][2])])
for i in range(N):
  for j in range(50*(N-1)):
    edge[i+N*j].append([L2[i][1],i+N*min(50*(N-1),j+L2[i][0])])
ans=[[] for i in range(N)]
D=dijkstra_heap(min(50*(N-1),s)*N)
for i in range(len(D)):
  ans[i%N].append(D[i])
for i in range(1,N):
  print((min(ans[i])))

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

def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

N,m,s=list(map(int,input().split()))
L=[list(map(int,input().split())) for i in range(m)]
L2=[list(map(int,input().split())) for i in range(N)]
n=N*(50*(N-1)+1)
edge=[[] for i in range(n)]
for i in range(m):
  for j in range(50*(N-1)+1):
    if j>=L[i][2]:
      edge[L[i][0]-1+N*j].append([L[i][3],L[i][1]-1+N*(j-L[i][2])])
      edge[L[i][1]-1+N*j].append([L[i][3],L[i][0]-1+N*(j-L[i][2])])
for i in range(N):
  for j in range(50*(N-1)):
    edge[i+N*j].append([L2[i][1],i+N*min(50*(N-1),j+L2[i][0])])
ans=[[] for i in range(N)]
D=dijkstra_heap(min(50*(N-1),s)*N)
for i in range(len(D)):
  ans[i%N].append(D[i])
for i in range(1,N):
  print((min(ans[i])))
# Original solution
import heapq

N, M, S = list(map(int, input().split()))
Map = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

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

Q = []
heapq.heappush(Q, (0, 0, S)) # 今の時間、場所、持っているお金
Ans = [-1] * N
Ans[0] = 0
while -1 in Ans:
    time, where, money = heapq.heappop(Q)
    if Ans[where] == -1:
        Ans[where] = time
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        heapq.heappush(Q, (time + take, nex, money - cost))
    heapq.heappush(Q, (time + Exchange[where][1], where, money + Exchange[where][0]))


for a in Ans[1:]:
    print(a)

# Optimized solution
import heapq

N, M, S = list(map(int, input().split()))
Map = [[] for _ in range(N)]
Ans = [[float('inf')] * 2500 for _ in range(N)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

for i in range(N):
    c, d = list(map(int, input().split()))
    Map[i].append((i, -c, d))

Q = []
heapq.heappush(Q, (0, 0, min(2499, S))) # 今の時間、場所、持っているお金
Ans[0][min(2499, S)] = 0
while Q:
    time, where, money = heapq.heappop(Q)
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        if Ans[nex][min(2499, money - cost)] > time + take:
            Ans[nex][min(2499, money - cost)] = time + take
            heapq.heappush(Q, (time + take, nex, money - cost))

for a in Ans[1:]:
    print((min(a)))
# Original solution
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print((min(s)))

if __name__ == "__main__":
    run()

# Optimized solution
import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print((min(dist[i])))
# Original solution
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))

    cd = [int(i) for i in sys.stdin.read().split()]
    C = [0]+ cd[::2]
    D = [0]+ cd[1::2]

    queue = []
    # (time, node, rest-coin)
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print((min(s)))

if __name__ == "__main__":
    run()

# Optimized solution
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    # (time, node, rest-coin)
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin >= n_coin and state[n_node][coin-n_coin] > n_time + time:
                state[n_node][coin - n_coin] = n_time + time
                heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print((min(s)))

if __name__ == "__main__":
    run()
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, M, S = mapint()
query = [[(-1, -1)]*N for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    query[u-1][v-1] = (a, b)
    query[v-1][u-1] = (a, b)
exchange = [list(mapint()) for _ in range(N)]

inf = 10**18
dp = [[inf]*(N*50) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    rate, time = exchange[now]
    if coin<N*50:
        i = 0
        while coin+rate*i<N*50:
            if t+i*time<dp[now][coin+rate*i]:
                dp[now][coin+rate*i] = t+i*time
                for nx in range(N):
                    a, b = query[now][nx]
                    if a!=-1 and coin+rate*i>=a and dp[nx][coin+rate*i-a]>t+i*time+b:
                        heapq.heappush(queue, (t+i*time+b, nx, coin+rate*i-a))
            i += 1
    else:
        coin = N*50-1
        if t<dp[now][coin]:
            dp[now][coin] = t
            for nx in range(N):
                a, b = query[now][nx]
                if a!=-1 and coin>=a and dp[nx][coin-a]>t+b:
                    heapq.heappush(queue, (t+b, nx, coin-a))  

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


# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, M, S = mapint()
S = min(S, N*50)
query = [[[] for _ in range(N*50+1)] for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    for coin in range(a, N*50+1):
        query[u-1][coin].append((v-1, a, b))
        query[v-1][coin].append((u-1, a, b))
for i in range(N):
    c, d = mapint()
    for coin in range(N*50+1):
        query[i][coin].append((i, -c, d))

inf = 10**18
dp = [[inf]*(N*50+1) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    qlis = query[now][coin]
    for nx, a, b in qlis:
        if 0<=coin-a:
            coin = min(coin, N*50+a)
            if t+b<dp[nx][coin-a]:
                dp[nx][coin-a] = t+b
                heapq.heappush(queue, (t+b, nx, coin-a))

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