CodeEff/ECCO huggingface dataset:
# Original solution
n,m,s=list(map(int,input().split()))
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=list(map(int,input().split()))
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=list(map(int,input().split()))
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
heappush(pq,(0,s*n))
while pq:
    weight,u = heappop(pq)
    if d[u]>weight:
        d[u]=weight
        for v,weight in edge[u]:
            heappush(pq,(d[u]+weight,v))
for i in range(1,n):
    print((d[i]))

# Optimized solution
n,m,s=list(map(int,input().split()))
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=list(map(int,input().split()))
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=list(map(int,input().split()))
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
s=s*n
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
d[s]=0
heappush(pq,(0,s))
while pq:
    dist,u = heappop(pq)
    for v,cost in edge[u]:
        if d[v]<=dist+cost:
            continue
        d[v]=dist+cost
        heappush(pq,(d[v],v))
for i in range(1,n):
    print((d[i]))
# Original solution
import heapq
def main():
    N, M, S = list(map(int, input().split()))
    money_max = 50*N
    S = min(S, money_max-1)
    dp = [[float("inf")]*(money_max) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ 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])
    for i in range(N):
        c, d = list(map(int, input().split()))
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0])
    time_min = [float("inf")]*N
    time_min[0] = 0
    while 0 < len(q):
        pre_time, p = heapq.heappop(q)
        if time_min[p] < pre_time:
            continue
        for i in range(money_max - exchange[p][0]):
            if dp[p][i] < float("inf"):
                dp[p][i+exchange[p][0]] = min(dp[p][i+exchange[p][0]], dp[p][i] + exchange[p][1])
        for to, money, time in G[p]:
            f = False
            for i in range(money, money_max):
                if dp[p][i] < float("inf") and dp[to][i-money] > dp[p][i] + time:
                    dp[to][i-money] = dp[p][i] + time
                    if dp[to][i-money] < time_min[to]:
                        time_min[to] = dp[to][i-money]
                    f = True
            if f:
                heapq.heappush(q, [time_min[to], to])
    for i in range(1, N):
        print((time_min[i]))

if __name__ == "__main__":
    main()

# Optimized solution
import heapq
def main():
    N, M, S = list(map(int, input().split()))
    money_max = 50*N
    S = min(S, money_max)
    dp = [[float("inf")]*(money_max+1) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ 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])
    for i in range(N):
        c, d = list(map(int, input().split()))
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0, S])
    while 0 < len(q):
        pre_time, idx, s = heapq.heappop(q)
        if dp[idx][s] < pre_time:
            continue
        ex = min(s + exchange[idx][0], money_max)
        if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
            dp[idx][ex] = dp[idx][s] + exchange[idx][1]
            heapq.heappush(q, [dp[idx][ex], idx, ex])
        for to, money, time in G[idx]:
            if money <= s:
                if dp[idx][s] + time < dp[to][s-money]:
                    dp[to][s-money] = dp[idx][s] + time
                    heapq.heappush(q, [dp[to][s-money], to, s-money])
    for i in range(1, N):
        print((min(dp[i])))

if __name__ == "__main__":
    main()
# Original solution
import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] < dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")


# Optimized solution
import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")
# Original solution
n,m,s = list(map(int,input().split()))
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = list(map(int,input().split()))
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = list(map(int,input().split()))
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(100):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print((arr[ii][0]))
#print(arr[0])

# Optimized solution
n,m,s = list(map(int,input().split()))
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = list(map(int,input().split()))
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = list(map(int,input().split()))
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(50):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print((arr[ii][0]))
#print(arr[0])
# Original solution
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = list(map(int,input().split()))

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
#T= copy.copy(V)


if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = list(map(int,input().split()))
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
T=set(range(Nv))
visited = set([1])
allcity = set(range(1,N+1))

s=V[(1,S)]
T.remove(s) #del T[s]
D[s] = 0
for v in T:
    D[v] = w[ s ][ v ]
#while len(T) > 0:
for _ in range(Nv-1):
    u = min(T,key=lambda x:D[x])
    T.remove(u)

    visited.add(u//(Ns+1)+1)
    if visited == allcity:
        break

    for v in T:
        D[ v ] = min( D[ v ], D[ u ] + w[ u ][ v ] )

for i in range(1,N):
    ans = min([D[i*(Ns+1)+v] for v in range(Ns+1)])
    print(ans)

# Optimized solution
import math
import heapq

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = list(map(int,input().split()))
    Us[i] -= 1
    Vs[i] -= 1

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

G=[[] for _ in range(Nv)]

if S > Ns:
    S = Ns

# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            G[ V[(u,ns_s)] ].append( (V[(v,ns_g)],b) )
            # V -> U
            G[ V[(v,ns_s)] ].append( (V[(u,ns_g)],b) )
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = list(map(int,input().split()))
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        G[ V[(i,ns_s)] ].append( (V[(i,ns_g)],d) )

# -----
D=[math.inf]*Nv
q=[]
# -----

s=V[(0,S)]
D[s] = 0
heapq.heappush(q,(0,s))

while len(q) > 0:
    p_cost,p_v = heapq.heappop(q)
    if D[p_v] < p_cost:
        continue
    for e_to,e_cost in G[p_v]:
        if D[ e_to ] > D[p_v] + e_cost:
            D[e_to] = D[p_v] + e_cost
            heapq.heappush(q, (D[e_to], e_to))

for i in range(1,N):
    ans = min([D[i*(Ns+1)+v] for v in range(Ns+1)])
    print(ans)
# Original solution
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*n
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in list(edge[p].items()):
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

def Dijkstra(start):
    inf = float('inf')
    d = [[inf]*(A+1) for _ in range(n)]
    d[start][min(s,A)] = 0
    pq = [(0,start,min(s,A))]
    heapq.heapify(pq)
    while pq:
        dist,p,money = heapq.heappop(pq)
        while True:
            if money >= A:
                money = A
            for to,(cost,time) in list(path[p].items()):
                if money < cost or d[to][money - cost] <= dist + time:continue
                d[to][money - cost] = dist + time
                heapq.heappush(pq, (d[to][money - cost],to,money - cost))
            if money == A:break
            money += C[p]
            dist += D[p]
        for to in list(path[p].keys()):
            m = inf
            for i in range(A+1)[::-1]:
                m = min(m,d[to][i])
                d[to][i] = m
    return d

n,m,s = list(map(int,input().split()))
path = [{} for _ in range(n)]
A = 0
for i in range(m):
    u,v,a,b = list(map(int,input().split()))
    A += a
    u -= 1
    v -= 1
    path[u][v] = (a,b)
    path[v][u] = (a,b)
A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = list(map(int,input().split()))
ans = Dijkstra(0)
for a in ans[1:]:
    print((min(a)))


# Optimized solution
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in list(edge[p].items()):
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = list(map(int,input().split()))
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = list(map(int,input().split()))
    # A += a
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = list(map(int,input().split()))

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in list(edge[i].items()):
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print((min(ans[i*(A+1):i*(A+1)+A+1])))
# Original solution
n, m, s = map(int,input().split())
adj = [[] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int,input().split())
    adj[u - 1].append((v - 1,-a,b))
    adj[v - 1].append((u - 1,-a,b))

for i in range(n):
    c, d = map(int,input().split())
    adj[i].append((i,c,d))

out = [-1] * n

LARGE = 10000

done = dict()
from heapq import *
q = []
if s > LARGE:
    s = LARGE
heappush(q, (0, 0, s))

while q:
    time, loc, curr = heappop(q)
    if out[loc] == -1:
        out[loc] = time
    for nex, cost, timeD in adj[loc]:
        currNex = curr + cost
        timeNex = time + timeD
        if currNex > LARGE:
            currNex = LARGE
        if currNex < 0:
            continue
        if (nex, currNex) not in done or timeNex < done[(nex, currNex)]:
            done[(nex, currNex)] = timeNex
            heappush(q, (timeNex, nex, currNex))
print(*out[1:], sep = '\n')
    


# Optimized solution
n, m, s = map(int,input().split())
adj = [[] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int,input().split())
    adj[u - 1].append((v - 1,-a,b))
    adj[v - 1].append((u - 1,-a,b))

for i in range(n):
    c, d = map(int,input().split())
    adj[i].append((i,c,d))

out = [-1] * n
count = 0

LARGE = 50 * n

done = dict()
from heapq import *
q = []
if s > LARGE:
    s = LARGE
heappush(q, (0, 0, s))

while q:
    time, loc, curr = heappop(q)
    if out[loc] == -1:
        out[loc] = time
        count += 1
        if count == n:
            break
    for nex, cost, timeD in adj[loc]:
        currNex = curr + cost
        timeNex = time + timeD
        if currNex > LARGE:
            currNex = LARGE
        if currNex < 0:
            continue
        if (nex, currNex) not in done or timeNex < done[(nex, currNex)]:
            done[(nex, currNex)] = timeNex
            heappush(q, (timeNex, nex, currNex))
print(*out[1:], sep = '\n')
# Original solution
N,M,S=list(map(int,input().split()))
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

# Optimized solution
N,M,S=list(map(int,input().split()))
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    if t>di[v]:
        continue
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)
# Original solution
N,M,S=list(map(int,input().split()))
from heapq import heappop,heappush 

inf = 10**18
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

# Optimized solution
N,M,S=list(map(int,input().split()))
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

S=min(S,2450)
di=[inf]*2451*N
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金
    if t>di[v]:
        continue

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    c=min(c,2450-s)
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=min(di[i*2451:(i+1)*2451])
    print(m)
# Original solution
n, m, s = list(map(int, input().split()))

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

banks = tuple(tuple(map(int, input().split())) for _ in range(n))

max_s = 50 * (n-1)

s = min(s, max_s)

import heapq

h = []
dp = [[float('inf')] * (max_s+1) for _ in range(n)]
ans = [float('inf')] * n

heapq.heappush(h, (0, 0, s))
while h:
    time, node, coin = heapq.heappop(h)
    if time < dp[node][coin]:
        dp[node][coin] = time
    if time < ans[node]:
        ans[node] = time

    c, d = banks[node]
    if coin < max_s:
        heapq.heappush(h, (time+d, node, min(coin + c, max_s)))

    for n, a, b in edges[node]:
        new_time = time + b
        new_coin = coin - a
        if new_coin < 0 or new_time >= dp[n][new_coin]:
            continue
        heapq.heappush(h, (new_time, n, new_coin))

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


# Optimized solution
n, m, s = list(map(int, input().split()))

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

banks = tuple(tuple(map(int, input().split())) for _ in range(n))

max_s = 50 * (n-1)

s = min(s, max_s)

import heapq

h = []
dp = [[float('inf')] * (max_s+1) for _ in range(n)]
ans = [float('inf')] * n

heapq.heappush(h, (0, 0, s))
while h:
    time, node, coin = heapq.heappop(h)
    if time >= dp[node][coin]:
        continue
    dp[node][coin] = time
    if time < ans[node]:
        ans[node] = time

    c, d = banks[node]
    if coin < max_s:
        heapq.heappush(h, (time+d, node, min(coin + c, max_s)))

    for n, a, b in edges[node]:
        new_time = time + b
        new_coin = coin - a
        if new_coin < 0 or new_time >= dp[n][new_coin]:
            continue
        heapq.heappush(h, (new_time, n, new_coin))

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