CodeEff/ECCO huggingface dataset:
# Original solution
import heapq

# https://nashidos.hatenablog.com/entry/2020/04/07/100508
def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * ((maxsilver+1)*n) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, w in e[v]:
            tmp = d + cost[v]
            if tmp < cost[w]:
                cost[w] = tmp
                heapq.heappush(hq, (tmp, w))
    return cost

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

u,v,a,b = [0]*m,[0]*m,[0]*m,[0]*m 
c,d = [0]*n,[0]*n 
for i in range(m):
    u[i],v[i],a[i],b[i] = list(map(int,input().split()))
for i in range(n):
    c[i],d[i] = list(map(int,input().split()))

maA = max(a)
maxsilver = maA*(n-1)
p = (maxsilver+1) * n
# 都市i(0~)で銀貨j枚持っている時,i*(maxsilver+1)+j番目
e = [[] for i in range(p)]
# 金貨交換
for i in range(n):
    for j in range(maxsilver+1):
        e[i*(maxsilver+1) + j].append((d[i], i*(maxsilver+1) + min(j+c[i], maxsilver)))
# 移動
for i in range(m):
    for j in range(a[i],maxsilver+1):
        e[(u[i]-1)*(maxsilver+1) + j].append((b[i], (v[i]-1)*(maxsilver+1) + j-a[i]))
        e[(v[i]-1)*(maxsilver+1) + j].append((b[i], (u[i]-1)*(maxsilver+1) + j-a[i]))

# print(e)
# 初期地点は0+min(s,maxsilver)
for i in range(1,n):
    ans = float("inf")
    x = [0]*(maxsilver+1)
    for j in range(maxsilver+1):
        x[j] =  dijkstra(min(s,maxsilver))[i*(maxsilver+1)+j]
    heapq.heapify(x)
    ans = heapq.heappop(x)
    print(ans)

# Optimized solution
import heapq

# https://nashidos.hatenablog.com/entry/2020/04/07/100508
def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * ((maxsilver+1)*n) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, w in e[v]:
            tmp = d + cost[v]
            if tmp < cost[w]:
                cost[w] = tmp
                heapq.heappush(hq, (tmp, w))
    return cost

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

u,v,a,b = [0]*m,[0]*m,[0]*m,[0]*m 
c,d = [0]*n,[0]*n 
for i in range(m):
    u[i],v[i],a[i],b[i] = list(map(int,input().split()))
for i in range(n):
    c[i],d[i] = list(map(int,input().split()))

maA = max(a)
maxsilver = maA*(n-1)
p = (maxsilver+1) * n
# 都市i(0~)で銀貨j枚持っている時,i*(maxsilver+1)+j番目
e = [[] for i in range(p)]
# 金貨交換
for i in range(n):
    for j in range(maxsilver+1):
        e[i*(maxsilver+1) + j].append((d[i], i*(maxsilver+1) + min(j+c[i], maxsilver)))
# 移動
for i in range(m):
    for j in range(a[i],maxsilver+1):
        e[(u[i]-1)*(maxsilver+1) + j].append((b[i], (v[i]-1)*(maxsilver+1) + j-a[i]))
        e[(v[i]-1)*(maxsilver+1) + j].append((b[i], (u[i]-1)*(maxsilver+1) + j-a[i]))

# print(e)
# 初期地点は0+min(s,maxsilver)
d = dijkstra(min(s,maxsilver))
for i in range(1,n):
    ans = float("inf")
    x = [0]*(maxsilver+1)
    for j in range(maxsilver+1):
        x[j] =  d[i*(maxsilver+1)+j]
    heapq.heapify(x)
    ans = heapq.heappop(x)
    print(ans)
# Original solution
import sys
input = lambda: sys.stdin.readline().rstrip()

n, m, s = list(map(int, input().split()))
s = min(s, 2500)
from collections import defaultdict
# O(ElogV)
import heapq
def dijkstra(s, x):
    # 始点sから各頂点への最短距離
    d = defaultdict(lambda: float("inf"))
    d[(s, x)] = 0
    # 各頂点が訪問済みかどうか
    used = defaultdict(lambda: False)
    used[(s, x)] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in edge[(s, x)]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, (e[0] + d[v], e[1]))
    return d

max_money = 2500
edge = defaultdict(list)
for _ in range(m):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    for i in range(a, max_money + 1):
        edge[(u, i)].append((b, (v, i - a)))
        edge[(v, i)].append((b, (u, i - a)))
for j in range(n):
    c, d = list(map(int, input().split()))
    for i in range(max_money):
        if i + c <= max_money:
            edge[(j, i)].append((d, (j, i + c)))

ans = [10**18]*n

d = dijkstra(0, s)
for i in d:
    x, y = i
    cost = d[i]
    ans[x] = min(ans[x], cost)
for i in ans[1:]:
    print(i)


# Optimized solution
def main(): 
    import sys
    input = lambda: sys.stdin.readline().rstrip()

    n, m, s = list(map(int, input().split()))
    s = min(s, 2500)
    from collections import defaultdict
    # O(ElogV)
    import heapq
    def dijkstra(s, x):
        # 始点sから各頂点への最短距離
        d = defaultdict(lambda: float("inf"))
        d[(s, x)] = 0
        # 各頂点が訪問済みかどうか
        used = defaultdict(lambda: False)
        used[(s, x)] = True
        # 仮の距離を記録するヒープ
        que = []
        for e in edge[(s, x)]:
            heapq.heappush(que, e)
        while que:
            minedge = heapq.heappop(que)
            if used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = True
            for e in edge[v]:
                if not used[e[1]]:
                    heapq.heappush(que, (e[0] + d[v], e[1]))
        return d

    max_money = 2500
    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        for i in range(a, max_money + 1):
            edge[(u, i)].append((b, (v, i - a)))
            edge[(v, i)].append((b, (u, i - a)))
    for j in range(n):
        c, d = list(map(int, input().split()))
        for i in range(max_money):
            if i + c <= max_money:
                edge[(j, i)].append((d, (j, i + c)))

    ans = [10**18]*n

    d = dijkstra(0, s)
    for i in d:
        x, y = i
        cost = d[i]
        ans[x] = min(ans[x], cost)
    for i in ans[1:]:
        print(i)
main()
# Original solution
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = list(map(int, input().split()))
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = list(map(int, input().split()))
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print(('\n'.join(map(str, ans[2:]))))

# Optimized solution
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = list(map(int, input().split()))
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = list(map(int, input().split()))
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print(('\n'.join(map(str, ans[2:]))))
# Original solution
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = list(map(int, input().split()))
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

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

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while 10**6 > len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            heappush(que, (cost + d, num, s_tmp))
            nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in list(edges[num].keys()):
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

dijakstra()
for i in range(1, n):
    print((min(nodes[i])))



# Optimized solution
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**19
n, m, s = list(map(int, input().split()))
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

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

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while 10**6 > len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            if nodes[num][s_tmp] > cost + d:
                heappush(que, (cost + d, num, s_tmp))
                nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in list(edges[num].keys()):
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

dijakstra()
for i in range(1, n):
    print((min(nodes[i])))
# Original solution
from heapq import heappop,heappush
inf = float("inf")

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

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

for i in range(n):
    cost,time = list(map(int,input().split()))
    G[i].append((i,-cost,time))

# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf]*2451 for _ in range(n)]

# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white]*2451 for _ in range(n)]

def dijkstra(u,s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s,2450)
    mint[u][s] = 0
    color[u][s] = black

    PQ = []
    heappush(PQ,(0,u,s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv,now,nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt,cost,time in G[now]:
            nxtcoins = min(nowcoins - cost,2450)
            if nxtcoins < 0: continue
            if color[nxt][nxtcoins]: continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))

dijkstra(0,s)

# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1,n): print((min(mint[i])))

# Optimized solution
from heapq import heappop,heappush
inf = float("inf")

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

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

for i in range(n):
    cost,time = list(map(int,input().split()))
    G[i].append((i,-cost,time))

# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf]*2451 for _ in range(n)]

# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white]*2451 for _ in range(n)]

def dijkstra(u,s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s,2450)
    mint[u][s] = 0
    color[u][s] = black

    PQ = []
    heappush(PQ,(0,u,s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv,now,nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        # 最小時間じゃないなら無視
        if mint[now][nowcoins] < minv: continue
        
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt,cost,time in G[now]:
            nxtcoins = min(nowcoins - cost,2450)
            if nxtcoins < 0: continue
            if color[nxt][nxtcoins]: continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))

dijkstra(0,s)

# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1,n): print((min(mint[i])))
# Original solution
import heapq
def dijkstra_heap(N,S,edge):
  d = [[float('inf')]*(N*100+1) for _ in range(N)] #始点0から各頂点への最短距離
  used = [[False]*(N*100+1) for _ in range(N)]
  d[0][S] = 0
  used[0][S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,v,sil in edge[0]:
    if S+sil>=0 and S+sil<=N*100:
      heapq.heappush(edgelist,[w,v,S+sil]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_v,min_sil = heapq.heappop(edgelist)
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_v][min_sil]:
      continue
    d[min_v][min_sil] = min_w
    used[min_v][min_sil] = True
    for w,v,sil in edge[min_v]:
      if min_sil+sil>=0 and min_sil+sil<=N*100 and not used[v][min_sil+sil]:
        heapq.heappush(edgelist,[min_w+w,v,min_sil+sil])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,v-1,-a])
    edge[v-1].append([b,u-1,-a])
  S = min(S,(N-1)*amax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i,c])
  D = dijkstra_heap(N,S,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i])
  return ans[1:]
print(*solve(),sep='\n')


# Optimized solution
import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')
# Original solution
# -*- coding:utf-8 -*-

def solve():
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    # dp[v][s] := 頂点vに所持金sで訪れるときの最小時間
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    # ダイクストラ
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  # (時刻t, 頂点番号v, 所持金s)
    # heapq.heappush(que, (0, s, 0))  # (頂点番号v, 所持金s, 時刻t)

    while len(que) != 0:
        t, v, s = heapq.heappop(que)
        # v, s, t = heapq.heappop(que)

        # if dp[v][s] != t: continue  # なにこれ？

        # 両替する場合
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))
            # heapq.heappush(que, (v, ns, t+d))

        # 移動する場合(v -> uに移動)
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))
                # heapq.heappush(que, (u, s-a, t+b))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


if __name__ == "__main__":
    solve()


# Optimized solution
# -*- coding:utf-8 -*-

def solve():
    """解説実装"""
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    # dp[v][s] := 頂点vに所持金sで訪れるときの最小時間
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    # ダイクストラ
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  # (時刻t, 頂点番号v, 所持金s)

    while len(que) != 0:
        t, v, s = heapq.heappop(que)

        # if dp[v][s] != t: continue  # なにこれ？

        # 両替する場合
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))

        # 移動する場合(v -> uに移動)
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


if __name__ == "__main__":
    solve()
# Original solution
import sys
input = sys.stdin.readline

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

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<64]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print((min(DP[i])))

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

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

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<60]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print((min(DP[i])))