CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq
  inf=pow(10,20)*5
  #dp=[[inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  #dp[0][min(s,100*51-1)]=0
  from collections import defaultdict
  dp=defaultdict(lambda:inf)
  dp[(0,min(s,100*51-1))]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[(v,j)]=min(dp[(v,j)],dp[(v,i)]+d)
      heapq.heappush(todo,[dp[(v,j)],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[(u,i-a)]=min(dp[(u,i-a)],dp[(v,i)]+b)
        heapq.heappush(todo,[dp[(u,i-a)],u,i-a])
  print(*ans[1:],sep='\n')

if __name__=='__main__':
  main()


# Optimized solution
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
# Original solution
n,m,s=list(map(int,input().split()))
uvab=[list(map(int,input().split())) for _ in range(m)]
cd=[list(map(int,input().split())) for _ in range(n)]
g=[[] for _ in range(n)]
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
maxs=50*m
ans=[[inf]*(maxs+1) for _ in range(n)]
s=min(s,maxs)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    c,d=cd[v]
    nss=min(ss+c,maxs)
    if ans[v][nss]>t+d:
        heappush(todo,[t+d,v,nss])
        ans[v][nss]=t+d
for i in range(1,n):
    print((min(ans[i])))


# Optimized solution
n,m,s=list(map(int,input().split()))
uvab=[list(map(int,input().split())) for _ in range(m)]
cd=[list(map(int,input().split())) for _ in range(n)]
g=[[] for _ in range(n)]
maxs=0
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])
    maxs+=a

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
ans=[[inf]*(maxs+1) for _ in range(n)]
s=min(s,maxs)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    c,d=cd[v]
    nss=min(ss+c,maxs)
    if ans[v][nss]>t+d:
        heappush(todo,[t+d,v,nss])
        ans[v][nss]=t+d
for i in range(1,n):
    print((min(ans[i])))
# Original solution
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = list(map(int, input().split()))
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in list(to[now].items()):
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        for i, ns in enumerate(list(range(s + rate, MAX_SILVER, rate)), 1):
            nt = t + time * i
            if cost[nv][ns] <= nt : continue
            heappush(q, (nt, now, ns))
    
    for i in range(1, N):
        print((min(cost[i])))

if __name__ == "__main__":
    main()

# Optimized solution
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = list(map(int, input().split()))
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in list(to[now].items()):
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print((min(cost[i])))

if __name__ == "__main__":
    main()
# Original solution
import heapq
INF = 10**20

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

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

M = 2500
S = min(S, M-1) # 2500枚あれば十分
dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数]
dist[0][S] = 0
q = [(0,S,0)] # (距離、銀貨の枚数、都市)

while q:
    d, sil, node = heapq.heappop(q)
    if dist[node][sil] < d: # 探索の対象にする必要があるか確認
        continue 
    if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]:
        dist[node][sil+C[node]] = d + D[node]
        heapq.heappush(q, (d + D[node], sil+C[node] ,node))
    for to,a,b in adj[node]:
        if sil >= a and d + b < dist[to][sil-a]:
            dist[to][sil-a] = d + b
            heapq.heappush(q, (d + b, sil-a ,to))

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



# Optimized solution
import heapq
INF = 10**20

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

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

M = 2500
S = min(S, M-1) # 2500枚あれば十分
dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数]
dist[0][S] = 0
pq = [(0,S,0)] # (時間、銀貨の枚数、都市)

while pq:
    d, sil, node = heapq.heappop(pq)
    if dist[node][sil] < d: # 探索の対象にする必要があるか確認
        continue 
     # 銀貨に交換したとして、上限を超えないか、探索の必要があるか
    if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]:
        dist[node][sil+C[node]] = d + D[node] # 時間の更新
        heapq.heappush(pq, (d + D[node], sil+C[node] ,node))
    for next, a, b in adj[node]:
        # 銀貨が足りるか、探索の必要があるか
        if sil >= a and d + b < dist[next][sil-a]:
            dist[next][sil-a] = d + b
            heapq.heappush(pq, (d + b, sil-a ,next))

for i in range(1,N):
    print((min(dist[i]))) # 残っている銀貨の枚数は問わない
# Original solution
from heapq import*
(n,m,s),*t=[list(map(int,t.split()))for t in open(0)]
*e,=eval('[],'*8**6)
for u,v,a,b in t[:m]:
    for i in range(2501-a):
        e[(i+a)*51+u]+=(b,i*51+v),
        e[(i+a)*51+v]+=(b,i*51+u),
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501-c):
        e[j*51+i]+=(d,(j+c)*51+i),
d=[10**18]*8**6
f=[1]*8**6
q=[(0,min(2500,s)*51+1)]
while q:
    c,v=heappop(q)
    if f[v]<1:continue
    d[v],f[v]=c,0
    for p,w in e[v]:
        if f[w]:heappush(q,(c+p,w))
for i in range(2,n+1):print((min(d[i::51])))

# Optimized solution
def main():
    from heapq import heappush,heappop
    (n,m,s),*t=[list(map(int,r.split()))for r in open(0)]
    e=[[]for _ in range(8**6)]
    for u,v,a,b in t[:m]:
        for i in range(2501-a):
            e[(i+a)*51+u]+=(b,i*51+v),
            e[(i+a)*51+v]+=(b,i*51+u),
    for i,(c,d)in enumerate(t[m:],1):
        for j in range(2501-c):
            e[j*51+i]+=(d,(j+c)*51+i),
    x=[10**18]*8**6
    f=[1]*8**6
    q=[(0,min(2500,s)*51+1)]
    while q:
        c,v=heappop(q)
        if f[v]<1:continue
        x[v],f[v]=c,0
        for p,w in e[v]:
            if f[w]:heappush(q,(c+p,w))
    for i in range(2,n+1):print((min(x[i::51])))
main()
# Original solution
import heapq

N, M, S = list(map(int, input().strip().split()))

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, A, B = list(map(int, input().strip().split()))
	u -= 1
	v -= 1
	graph[u].append((v, A, B))
	graph[v].append((u, A, B))

exchanges = []
for _ in range(N):
	C, D = list(map(int, input().strip().split()))
	exchanges.append((C, D))

queue = [(0, 0, S)]

state_table = [[None] * (2500 + 1) for i in range(N)]

reached = [False] * N
reached_count = 0

while queue:
#	print(len(queue))
	time, cur, money = heapq.heappop(queue)
	if not reached[cur]:
		reached[cur] = True
		reached_count += 1
		if reached_count >= N:
			break
	count, d_time = exchanges[cur]
	for n, A, B in graph[cur]:
		n_money = money - A
		n_time = time + B
		states = state_table[n]
		max_fare = 2500
		while True:
			if n_money >= 0:
				if n_money > max_fare:
					n_money = max_fare
				if states[n_money] == None or states[n_money] > n_time:
					states[n_money] = n_time
					heapq.heappush(queue, (n_time, n, n_money))
				if n_money >= max_fare:
					break
			n_money += count
			n_time += d_time

#for i in range(N):
#	print(i, state_table[i])

for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)


# Optimized solution
import heapq

N, M, S = list(map(int, input().strip().split()))

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, A, B = list(map(int, input().strip().split()))
	u -= 1
	v -= 1
	graph[u].append((v, A, B))
	graph[v].append((u, A, B))

exchanges = []
for _ in range(N):
	C, D = list(map(int, input().strip().split()))
	exchanges.append((C, D))

queue = [(0, 0, S)]
max_fare = 2500

state_table = [[None] * (max_fare + 1) for i in range(N)]

reached = [False] * N
reached_count = 0

while queue:
#	print(len(queue))
	time, cur, money = heapq.heappop(queue)
	if not reached[cur]:
		reached[cur] = True
		reached_count += 1
		if reached_count >= N:
			break
	count, d_time = exchanges[cur]
	for n, A, B in graph[cur]:
		n_money = money - A
		n_time = time + B
		if n_money >= 0:
			states = state_table[n]
			if n_money > max_fare:
				n_money = max_fare
			if states[n_money] == None or states[n_money] > n_time:
				states[n_money] = n_time
				heapq.heappush(queue, (n_time, n, n_money))

	states = state_table[cur]
	money += count
	time += d_time
	if money >= 0:
		if money > max_fare:
			money = max_fare
		if states[money] == None or states[money] > time:
			states[money] = time
			heapq.heappush(queue, (time, cur, money))

#for i in range(N):
#	print(i, state_table[i])

for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)
# Original solution
def solve():
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [(0,start)]
    ans = [-1] * N
    ans[0] = 0
    reached = set()
    import heapq
    heapq.heapify(hq)
    while hq:
        t,v = heapq.heappop(hq)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached.add(i)
            if len(reached) == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b, nv))
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, (nt, nv))
    print(*ans[1:], sep='\n')
solve()


# Optimized solution
def solve():
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = set()
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached.add(i)
            if len(reached) == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()
# Original solution
def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()


# Optimized solution
def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: break
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()
# Original solution
import heapq


n, m, s = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))

    
dist = [INF] * (3001 * n)
dist[min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * 3001 + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v * 3001 + tmp + cc] > dist[v * 3001 + tmp] + dd:
                dist[v * 3001 + tmp + cc] = dist[v * 3001 + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * 3001 + g] + time < dist[nxt_v * 3001 + g - cost]:
                dist[nxt_v * 3001 + g - cost] = dist[v * 3001 + g] + time
                heapq.heappush(q, (dist[nxt_v * 3001 + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print((min(dist[i * 3001:(i + 1) * 3001])))


# Optimized solution
import heapq


n, m, s = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print((min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)])))
# Original solution
class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])

n,m,s = list(map(int, input().split()))
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = list(map(int, input().split()))
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [RangeMinimumQuery(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur].query(money, max_money+1) <= time:
        continue
    state[cur].update(money, time)
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to].query(money-a, max_money+1) <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print((state[i].query(0, max_money+1)))


# Optimized solution
max_s = 2500

n,m,s = list(map(int, input().split()))
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = list(map(int, input().split()))
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = list(map(int, input().split()))
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)