import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7 # 998244353

input=lambda:sys.stdin.readline().rstrip()

def resolve():

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

    E = [None] * m

    S = 0

    for i in range(m):

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

        S += a

        E[i] = (u - 1, v - 1, -a, b)



    exchange = [tuple(map(int,input().split())) for _ in range(n)]

    dp = [[INF] * (S + 1) for _ in range(n)]

    dp[0][min(s, S)] = 0



    for _ in range(2 * n - 3):

        # 先に両替を済ませる

        for v in range(n):

            for s in range(S + 1):

                ds, dt = exchange[v]

                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)

        # 移動する

        for u, v, ds, dt in E:

            for s in range(S + 1):

                ns = s + ds

                if ns < 0:

                    continue

                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)

                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)



    for v in range(1, n):

        print((min(dp[v][j] for j in range(S + 1))))

resolve()
import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7 # 998244353

input=lambda:sys.stdin.readline().rstrip()

from heapq import heappop, heappush

def resolve():

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

    S = 0

    E = [[] for _ in range(n)]

    for _ in range(m):

        u, v, a, b = list(map(int,input().split())) # a : cost silver

        u -= 1; v -= 1

        S += a

        E[u].append((v, -a, b))

        E[v].append((u, -a, b))

    for v in range(n):

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

        E[v].append((v, c, d))



    # Dijkstra with heap

    dist = [[INF] * (S + 1) for _ in range(n)]

    s = min(s, S)

    dist[0][s] = 0

    heap = [(0, 0, s)] # dist, vertex, silver

    while heap:

        d, v, s = heappop(heap)

        if dist[v][s] < d:

            continue

        for nv, ds, dd in E[v]:

            ns = s + ds

            if not (0 <= ns <= S):

                continue

            if dist[nv][ns] > dist[v][s] + dd:

                dist[nv][ns] = dist[v][s] + dd

                heappush(heap, (dist[nv][ns], nv, ns))



    # output

    for v in range(1, n):

        print((min(dist[v][s] for s in range(S + 1))))

resolve()
import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7  # 998244353
input = lambda: sys.stdin.readline().rstrip()


def resolve():
    n, m, s = list(map(int, input().split()))
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = list(map(int, input().split()))
        S += a
        E[i] = (u - 1, v - 1, -a, b)
    exchange = [tuple(map(int, input().split())) for _ in range(n)]
    dp = [[INF] * (S + 1) for _ in range(n)]
    dp[0][min(s, S)] = 0
    for _ in range(2 * n - 3):
        # 先に両替を済ませる
        for v in range(n):
            for s in range(S + 1):
                ds, dt = exchange[v]
                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
        # 移動する
        for u, v, ds, dt in E:
            for s in range(S + 1):
                ns = s + ds
                if ns < 0:
                    continue
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
    for v in range(1, n):
        print((min(dp[v][j] for j in range(S + 1))))


resolve()

import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7  # 998244353
input = lambda: sys.stdin.readline().rstrip()
from heapq import heappop, heappush


def resolve():
    n, m, s = list(map(int, input().split()))
    S = 0
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = list(map(int, input().split()))  # a : cost silver
        u -= 1
        v -= 1
        S += a
        E[u].append((v, -a, b))
        E[v].append((u, -a, b))
    for v in range(n):
        c, d = list(map(int, input().split()))
        E[v].append((v, c, d))
    # Dijkstra with heap
    dist = [[INF] * (S + 1) for _ in range(n)]
    s = min(s, S)
    dist[0][s] = 0
    heap = [(0, 0, s)]  # dist, vertex, silver
    while heap:
        d, v, s = heappop(heap)
        if dist[v][s] < d:
            continue
        for nv, ds, dd in E[v]:
            ns = s + ds
            if not (0 <= ns <= S):
                continue
            if dist[nv][ns] > dist[v][s] + dd:
                dist[nv][ns] = dist[v][s] + dd
                heappush(heap, (dist[nv][ns], nv, ns))
    # output
    for v in range(1, n):
        print((min(dist[v][s] for s in range(S + 1))))


resolve()

+from heapq import heappop, heappush -    E = [None] * m -    for i in range(m): -        u, v, a, b = list(map(int, input().split())) +    E = [[] for _ in range(n)] +    for _ in range(m): +        u, v, a, b = list(map(int, input().split()))  # a : cost silver +        u -= 1 +        v -= 1 -        E[i] = (u - 1, v - 1, -a, b) -    exchange = [tuple(map(int, input().split())) for _ in range(n)] -    dp = [[INF] * (S + 1) for _ in range(n)] -    dp[0][min(s, S)] = 0 -    for _ in range(2 * n - 3): -        # 先に両替を済ませる -        for v in range(n): -            for s in range(S + 1): -                ds, dt = exchange[v] -                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt) -        # 移動する -        for u, v, ds, dt in E: -            for s in range(S + 1): -                ns = s + ds -                if ns < 0: -                    continue -                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt) -                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt) +        E[u].append((v, -a, b)) +        E[v].append((u, -a, b)) +    for v in range(n): +        c, d = list(map(int, input().split())) +        E[v].append((v, c, d)) +    # Dijkstra with heap +    dist = [[INF] * (S + 1) for _ in range(n)] +    s = min(s, S) +    dist[0][s] = 0 +    heap = [(0, 0, s)]  # dist, vertex, silver +    while heap: +        d, v, s = heappop(heap) +        if dist[v][s] < d: +            continue +        for nv, ds, dd in E[v]: +            ns = s + ds +            if not (0 <= ns <= S): +                continue +            if dist[nv][ns] > dist[v][s] + dd: +                dist[nv][ns] = dist[v][s] + dd +                heappush(heap, (dist[nv][ns], nv, ns)) +    # output -        print((min(dp[v][j] for j in range(S + 1)))) +        print((min(dist[v][s] for s in range(S + 1))))