# coding: utf-8

import sys

from heapq import heapify, heappop, heappush



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

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))

N, M, S = lr()

UVAB = [lr() for _ in range(M)]

CD = [lr() for _ in range(N)]  # 0-indexed

Amax = 0

for i in range(M):

    a = UVAB[i][2]

    if a > Amax:

        Amax = a



limit = Amax*(N-1)

S = min(S, limit)

graph = [[] for _ in range(N+1)] # 1-indexed

for u, v, a, b in UVAB:

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

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



def dijkstra(start):

    # 時間、銀貨の枚数、現在地をqueへ

    INF = 10 ** 15

    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]

    dist[1][S] = 0

    que = [(0, S, 1)]

    while que:

        time, silver, prev = heappop(que)

        if dist[prev][silver] < time:

            continue

        for next, a, b in graph[prev]:

            t = time + b

            si = silver - a

            if si < 0:

                continue

            if dist[next][si] > t:

                dist[next][si] = t

                heappush(que, (t, si, next))

        c, d = CD[prev-1]

        si = min(limit, silver+c)

        while dist[prev][si] > time + d:

            dist[prev][si] = time + d

            heappush(que, (time+d, si, prev))

            si += c; si = min(limit, si)

            time += d

            

    return dist



dist = dijkstra(1)

for i in range(2, N+1):

    d = dist[i]

    answer = min(d)

    print(answer)



# 52
# coding: utf-8

import sys

from heapq import heapify, heappop, heappush



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

ir = lambda: int(sr())

lr = lambda: list(map(int, sr().split()))



# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra

N, M, S = lr()

limit = 2500

S = min(S, limit)

graph = [[] for _ in range((N+1) * (limit+1))]  # 1-indexed

for _ in range(M):

    u, v, a, b = lr()

    for x in range(a, limit+1):

        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))

        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))



for i in range(N):

    i += 1

    c, d = lr()

    for x in range(limit-c+1):

        graph[i*(limit+1) + x].append((i*(limit+1) + x + c, d))



def dijkstra(start):

    INF = 10 ** 15

    dist = [INF] * ((N+1) * (limit+1))

    dist[start] = 0

    que = [(0, start)]

    while que:

        d, prev = heappop(que)

        if dist[prev] < d:

            continue

        for next, time in graph[prev]:

            d1 = d + time

            if dist[next] > d1:

                dist[next] = d1

                heappush(que, (d1, next))

    return dist



dist = dijkstra(1*(limit+1)+S)

for i in range(2, N+1):

    answer = min(dist[i*(limit+1):(i+1)*(limit+1)])

    print(answer)

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a
limit = Amax * (N - 1)
S = min(S, limit)
graph = [[] for _ in range(N + 1)]  # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))


def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10**15
    dist = [[INF for _ in range(limit + 1)] for _ in range(N + 1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev - 1]
        si = min(limit, silver + c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time + d, si, prev))
            si += c
            si = min(limit, si)
            time += d
    return dist


dist = dijkstra(1)
for i in range(2, N + 1):
    d = dist[i]
    answer = min(d)
    print(answer)
# 52

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra
N, M, S = lr()
limit = 2500
S = min(S, limit)
graph = [[] for _ in range((N + 1) * (limit + 1))]  # 1-indexed
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit + 1):
        graph[u * (limit + 1) + x].append(((v * (limit + 1) + x - a), b))
        graph[v * (limit + 1) + x].append(((u * (limit + 1) + x - a), b))
for i in range(N):
    i += 1
    c, d = lr()
    for x in range(limit - c + 1):
        graph[i * (limit + 1) + x].append((i * (limit + 1) + x + c, d))


def dijkstra(start):
    INF = 10**15
    dist = [INF] * ((N + 1) * (limit + 1))
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, time in graph[prev]:
            d1 = d + time
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist


dist = dijkstra(1 * (limit + 1) + S)
for i in range(2, N + 1):
    answer = min(dist[i * (limit + 1) : (i + 1) * (limit + 1)])
    print(answer)

-# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1)) +# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra -UVAB = [lr() for _ in range(M)] -CD = [lr() for _ in range(N)]  # 0-indexed -Amax = 0 -for i in range(M): -    a = UVAB[i][2] -    if a > Amax: -        Amax = a -limit = Amax * (N - 1) +limit = 2500 -graph = [[] for _ in range(N + 1)]  # 1-indexed -for u, v, a, b in UVAB: -    graph[u].append((v, a, b)) -    graph[v].append((u, a, b)) +graph = [[] for _ in range((N + 1) * (limit + 1))]  # 1-indexed +for _ in range(M): +    u, v, a, b = lr() +    for x in range(a, limit + 1): +        graph[u * (limit + 1) + x].append(((v * (limit + 1) + x - a), b)) +        graph[v * (limit + 1) + x].append(((u * (limit + 1) + x - a), b)) +for i in range(N): +    i += 1 +    c, d = lr() +    for x in range(limit - c + 1): +        graph[i * (limit + 1) + x].append((i * (limit + 1) + x + c, d)) -    # 時間、銀貨の枚数、現在地をqueへ -    dist = [[INF for _ in range(limit + 1)] for _ in range(N + 1)] -    dist[1][S] = 0 -    que = [(0, S, 1)] +    dist = [INF] * ((N + 1) * (limit + 1)) +    dist[start] = 0 +    que = [(0, start)] -        time, silver, prev = heappop(que) -        if dist[prev][silver] < time: +        d, prev = heappop(que) +        if dist[prev] < d: -        for next, a, b in graph[prev]: -            t = time + b -            si = silver - a -            if si < 0: -                continue -            if dist[next][si] > t: -                dist[next][si] = t -                heappush(que, (t, si, next)) -        c, d = CD[prev - 1] -        si = min(limit, silver + c) -        while dist[prev][si] > time + d: -            dist[prev][si] = time + d -            heappush(que, (time + d, si, prev)) -            si += c -            si = min(limit, si) -            time += d +        for next, time in graph[prev]: +            d1 = d + time +            if dist[next] > d1: +                dist[next] = d1 +                heappush(que, (d1, next)) -dist = dijkstra(1) +dist = dijkstra(1 * (limit + 1) + S) -    d = dist[i] -    answer = min(d) +    answer = min(dist[i * (limit + 1) : (i + 1) * (limit + 1)]) -# 52