import heapq



def main():

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

    AB = [[] for _ in range(N)]

    maxA = 0

    for _ in range(M):

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

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

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

        maxA = max(maxA, a)

    for i in range(N):

        AB[i].sort()



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

    maxS = N * maxA

    cur = [(0, 0, S)]  # (time, station, silver)

    T = [-1] * N

    tc = N

    P = [-1] * N

    while tc:

        t, u, s = heapq.heappop(cur)

        if s <= P[u]:

            continue

        P[u] = s

        if T[u] == -1:

            T[u] = t

            tc -= 1

        for a, b, v in AB[u]:

            if s < a:

                break

            heapq.heappush(cur, (t + b, v, s - a))

        if s != maxS:

            c, d = CD[u]

            min_a = AB[u][0][0]

            k = max(1, (min_a - s + c  - 1) // c)

            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))

    print(('\n'.join(map(str, T[1:]))))



main()

import heapq



def main():

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

    AB = [[] for _ in range(N)]

    maxA = 0

    for _ in range(M):

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

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

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

        maxA = max(maxA, a)

    for i in range(N):

        AB[i].sort()



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

    maxS = N * maxA

    cur = [(0, 0, S)]  # (time, station, silver)

    T = [-1] * N

    tc = N

    P = [-1] * N

    while tc:

        t, u, s = heapq.heappop(cur)

        if s <= P[u]:

            continue

        P[u] = s

        if T[u] == -1:

            T[u] = t

            tc -= 1

        for a, b, v in AB[u]:

            if s < a:

                break

            if P[v] < s - a:

                heapq.heappush(cur, (t + b, v, s - a))

        if s != maxS:

            c, d = CD[u]

            min_a = AB[u][0][0]

            k = max(1, (min_a - s + c  - 1) // c)

            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))

    print(('\n'.join(map(str, T[1:]))))



main()

import heapq


def main():
    N, M, S = list(map(int, input().split()))
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    P = [-1] * N
    while tc:
        t, u, s = heapq.heappop(cur)
        if s <= P[u]:
            continue
        P[u] = s
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (min_a - s + c - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print(("\n".join(map(str, T[1:]))))


main()

import heapq


def main():
    N, M, S = list(map(int, input().split()))
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    P = [-1] * N
    while tc:
        t, u, s = heapq.heappop(cur)
        if s <= P[u]:
            continue
        P[u] = s
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            if P[v] < s - a:
                heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (min_a - s + c - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print(("\n".join(map(str, T[1:]))))


main()

-            heapq.heappush(cur, (t + b, v, s - a)) +            if P[v] < s - a: +                heapq.heappush(cur, (t + b, v, s - a))