# -*- 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()

# -*- 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()

# -*- 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()

# -*- 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()

+    """解説実装""" -    # heapq.heappush(que, (0, s, 0))  # (頂点番号v, 所持金s, 時刻t) -        # v, s, t = heapq.heappop(que) -            # heapq.heappush(que, (v, ns, t+d)) -                # heapq.heappush(que, (u, s-a, t+b))