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)

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

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

-import sys +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 +    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 +    # 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) -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()