from heapq import heappush, heappop



infi = 10 ** 20

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



s = min(s, 2500)



edges = [[] for _ in range(51 * 2501 + 1)]

# edge:1-50, max silver=0-2500



for _ in range(m):

    u, v, a, b = map(int, input().split())

    for i in range(a, 2501):

        edges[v + 50 * i].append((b, u + 50 * (i - a)))

        edges[u + 50 * i].append((b, v + 50 * (i - a)))





for edge_num in range(1, n + 1):

    c, d = map(int, input().split())

    # c枚, d分

    for i in range(2501):

        # 点edge_num+ i * 50のところに

        if edge_num + (i + c) * 50 <= 51 * 2501:

            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))

start = 1 + 50 * s





def dijkstra(edges, start):

    time = [infi] * (51 * 2501 + 1)

    used = [False] * (51 * 2501 + 1)

    time[start] = 0

    edgelist = []

    heappush(edgelist, (0, start))

    while edgelist:

        nowtime, nowedge = heappop(edgelist)

        if used[nowedge] is True:

            continue

        used[nowedge] = True

        time[nowedge] = nowtime

        for vt, v in edges[nowedge]:

            if used[v] is True:

                continue

            newtime = nowtime + vt

            heappush(edgelist, (newtime, v))

    return time





time = dijkstra(edges, start)



ans = [infi] * (51)

for i in range(1, 51 * 2501 + 1):

    temp = time[i]

    a = i % 50

    if a == 0:

        a += 50

    ans[a] = min(temp, ans[a])



print(*ans[2 : (n + 1)], sep="\n")

# snuke解説板

from heapq import heappush, heappop



infi = 10 ** 20

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



s = min(s, n * 50)



edges = [[] for _ in range(n + 1)]

# edge:1-50, max silver=0-2500



for _ in range(m):  # a円, b分

    u, v, a, b = map(int, input().split())

    edges[v].append((u, a, b))

    edges[u].append((v, a, b))



exchange = [(0, 0)] * (n + 1)



for edge_num in range(1, n + 1):  # c円, d分

    c, d = map(int, input().split())

    exchange[edge_num] = (c, d)



start = 1

# dp[i][j], 頂点iにお金jを持って到達する最低時間→時間に関してDAG

dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]





def dijkstra(edges, start, s, dp):

    dp[start][s] = 0

    edgelist = []

    heappush(edgelist, (0, s, start))  # 時間, お金, 頂点

    while edgelist:

        nowtime, nowmoney, nowedge = heappop(edgelist)

        # 遷移させる条件はedge,moneyの組み合わせに対してその時の最小値が出てきたときのみ→最小値以外は飛ばす。

        if dp[nowedge][nowmoney] != nowtime:

            continue

        # 両替

        deltamoney, deltatime = exchange[nowedge]

        nextmoney = min(nowmoney + deltamoney, n * 50)

        nexttime = nowtime + deltatime

        if dp[nowedge][nextmoney] > nexttime:

            dp[nowedge][nextmoney] = nexttime

            heappush(edgelist, (nexttime, nextmoney, nowedge))

        # 移動

        for v, vmoney, vtime in edges[nowedge]:

            nexttime = nowtime + vtime

            nextmoney = nowmoney - vmoney

            if nextmoney < 0:

                continue

            if dp[v][nextmoney] > nexttime:

                dp[v][nextmoney] = nexttime

                heappush(edgelist, (nexttime, nextmoney, v))

    return dp





time = dijkstra(edges, start, s, dp)



ans = [infi] * (n + 1)

for i in range(1, n + 1):

    for j in range(n * 50 + 1):

        ans[i] = min(ans[i], dp[i][j])



print(*ans[2 : (n + 1)], sep="\n")

from heapq import heappush, heappop

infi = 10**20
n, m, s = map(int, input().split())
s = min(s, 2500)
edges = [[] for _ in range(51 * 2501 + 1)]
# edge:1-50, max silver=0-2500
for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))
for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    # c枚, d分
    for i in range(2501):
        # 点edge_num+ i * 50のところに
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)
ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])
print(*ans[2 : (n + 1)], sep="\n")

# snuke解説板
from heapq import heappush, heappop

infi = 10**20
n, m, s = map(int, input().split())
s = min(s, n * 50)
edges = [[] for _ in range(n + 1)]
# edge:1-50, max silver=0-2500
for _ in range(m):  # a円, b分
    u, v, a, b = map(int, input().split())
    edges[v].append((u, a, b))
    edges[u].append((v, a, b))
exchange = [(0, 0)] * (n + 1)
for edge_num in range(1, n + 1):  # c円, d分
    c, d = map(int, input().split())
    exchange[edge_num] = (c, d)
start = 1
# dp[i][j], 頂点iにお金jを持って到達する最低時間→時間に関してDAG
dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]


def dijkstra(edges, start, s, dp):
    dp[start][s] = 0
    edgelist = []
    heappush(edgelist, (0, s, start))  # 時間, お金, 頂点
    while edgelist:
        nowtime, nowmoney, nowedge = heappop(edgelist)
        # 遷移させる条件はedge,moneyの組み合わせに対してその時の最小値が出てきたときのみ→最小値以外は飛ばす。
        if dp[nowedge][nowmoney] != nowtime:
            continue
        # 両替
        deltamoney, deltatime = exchange[nowedge]
        nextmoney = min(nowmoney + deltamoney, n * 50)
        nexttime = nowtime + deltatime
        if dp[nowedge][nextmoney] > nexttime:
            dp[nowedge][nextmoney] = nexttime
            heappush(edgelist, (nexttime, nextmoney, nowedge))
        # 移動
        for v, vmoney, vtime in edges[nowedge]:
            nexttime = nowtime + vtime
            nextmoney = nowmoney - vmoney
            if nextmoney < 0:
                continue
            if dp[v][nextmoney] > nexttime:
                dp[v][nextmoney] = nexttime
                heappush(edgelist, (nexttime, nextmoney, v))
    return dp


time = dijkstra(edges, start, s, dp)
ans = [infi] * (n + 1)
for i in range(1, n + 1):
    for j in range(n * 50 + 1):
        ans[i] = min(ans[i], dp[i][j])
print(*ans[2 : (n + 1)], sep="\n")

+# snuke解説板 -s = min(s, 2500) -edges = [[] for _ in range(51 * 2501 + 1)] +s = min(s, n * 50) +edges = [[] for _ in range(n + 1)] -for _ in range(m): +for _ in range(m):  # a円, b分 -    for i in range(a, 2501): -        edges[v + 50 * i].append((b, u + 50 * (i - a))) -        edges[u + 50 * i].append((b, v + 50 * (i - a))) -for edge_num in range(1, n + 1): +    edges[v].append((u, a, b)) +    edges[u].append((v, a, b)) +exchange = [(0, 0)] * (n + 1) +for edge_num in range(1, n + 1):  # c円, d分 -    # c枚, d分 -    for i in range(2501): -        # 点edge_num+ i * 50のところに -        if edge_num + (i + c) * 50 <= 51 * 2501: -            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50)) -start = 1 + 50 * s +    exchange[edge_num] = (c, d) +start = 1 +# dp[i][j], 頂点iにお金jを持って到達する最低時間→時間に関してDAG +dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)] -def dijkstra(edges, start): -    time = [infi] * (51 * 2501 + 1) -    used = [False] * (51 * 2501 + 1) -    time[start] = 0 +def dijkstra(edges, start, s, dp): +    dp[start][s] = 0 -    heappush(edgelist, (0, start)) +    heappush(edgelist, (0, s, start))  # 時間, お金, 頂点 -        nowtime, nowedge = heappop(edgelist) -        if used[nowedge] is True: +        nowtime, nowmoney, nowedge = heappop(edgelist) +        # 遷移させる条件はedge,moneyの組み合わせに対してその時の最小値が出てきたときのみ→最小値以外は飛ばす。 +        if dp[nowedge][nowmoney] != nowtime: -        used[nowedge] = True -        time[nowedge] = nowtime -        for vt, v in edges[nowedge]: -            if used[v] is True: +        # 両替 +        deltamoney, deltatime = exchange[nowedge] +        nextmoney = min(nowmoney + deltamoney, n * 50) +        nexttime = nowtime + deltatime +        if dp[nowedge][nextmoney] > nexttime: +            dp[nowedge][nextmoney] = nexttime +            heappush(edgelist, (nexttime, nextmoney, nowedge)) +        # 移動 +        for v, vmoney, vtime in edges[nowedge]: +            nexttime = nowtime + vtime +            nextmoney = nowmoney - vmoney +            if nextmoney < 0: -            newtime = nowtime + vt -            heappush(edgelist, (newtime, v)) -    return time +            if dp[v][nextmoney] > nexttime: +                dp[v][nextmoney] = nexttime +                heappush(edgelist, (nexttime, nextmoney, v)) +    return dp -time = dijkstra(edges, start) -ans = [infi] * (51) -for i in range(1, 51 * 2501 + 1): -    temp = time[i] -    a = i % 50 -    if a == 0: -        a += 50 -    ans[a] = min(temp, ans[a]) +time = dijkstra(edges, start, s, dp) +ans = [infi] * (n + 1) +for i in range(1, n + 1): +    for j in range(n * 50 + 1): +        ans[i] = min(ans[i], dp[i][j])