import sys

def input(): return sys.stdin.readline().strip()

def mapint(): return list(map(int, input().split()))

sys.setrecursionlimit(10**9)



N, M, S = mapint()

S = min(S, N*50)

query = [[[] for _ in range(N*50+1)] for _ in range(N)]

for _ in range(M):

    u, v, a, b = mapint()

    for coin in range(a, N*50+1):

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

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

for i in range(N):

    c, d = mapint()

    for coin in range(N*50+1):

        query[i][coin].append((i, -c, d))



inf = 10**18

dp = [[inf]*(N*50+1) for _ in range(N)]

dp[0][0] = 0



import heapq

queue = [(0, 0, S)]

checked = [0]*N

cnt = 0



while queue:

    t, now, coin = heapq.heappop(queue)

    if cnt==N:

        break

    if not checked[now]:

        checked[now] = 1

        cnt += 1

    qlis = query[now][coin]

    for nx, a, b in qlis:

        if 0<=coin-a:

            coin = min(coin, N*50+a)

            if t+b<dp[nx][coin-a]:

                dp[nx][coin-a] = t+b

                heapq.heappush(queue, (t+b, nx, coin-a))



for i in range(1, N):

    print((min(dp[i])))

import sys

def input(): return sys.stdin.readline().strip()

def mapint(): return list(map(int, input().split()))

sys.setrecursionlimit(10**9)



N, M, S = mapint()

graph = [{} for _ in range(N)]

for _ in range(M):

    u, v, a, t = mapint()

    graph[u-1][v-1] = (a, t)

    graph[v-1][u-1] = (a, t)



change = [list(mapint()) for _ in range(N)]

from heapq import heappop, heappush

# time, silver, vertex

Q = [(0, min(2500, S), 0)]

dist = [[10**18]*2501 for _ in range(N)]

dist[0][min(2500, S)] = 0



while Q:

    t, s, v = heappop(Q)

    rate, change_time = change[v]

    if s<2500 and dist[v][min(2500, s+rate)]>t+change_time:

        dist[v][min(2500, s+rate)] = t+change_time

        heappush(Q, (t+change_time, min(2500, s+rate), v))

    for nx in list(graph[v].keys()):

        nx_s, nx_t = graph[v][nx]

        if nx_s<=s and dist[nx][s-nx_s]>t+nx_t:

            dist[nx][s-nx_s] = t+nx_t

            heappush(Q, (t+nx_t, s-nx_s, nx))

for i in range(1, N):

    print((min(dist[i])))
import sys


def input():
    return sys.stdin.readline().strip()


def mapint():
    return list(map(int, input().split()))


sys.setrecursionlimit(10**9)
N, M, S = mapint()
S = min(S, N * 50)
query = [[[] for _ in range(N * 50 + 1)] for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    for coin in range(a, N * 50 + 1):
        query[u - 1][coin].append((v - 1, a, b))
        query[v - 1][coin].append((u - 1, a, b))
for i in range(N):
    c, d = mapint()
    for coin in range(N * 50 + 1):
        query[i][coin].append((i, -c, d))
inf = 10**18
dp = [[inf] * (N * 50 + 1) for _ in range(N)]
dp[0][0] = 0
import heapq

queue = [(0, 0, S)]
checked = [0] * N
cnt = 0
while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt == N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    qlis = query[now][coin]
    for nx, a, b in qlis:
        if 0 <= coin - a:
            coin = min(coin, N * 50 + a)
            if t + b < dp[nx][coin - a]:
                dp[nx][coin - a] = t + b
                heapq.heappush(queue, (t + b, nx, coin - a))
for i in range(1, N):
    print((min(dp[i])))

import sys


def input():
    return sys.stdin.readline().strip()


def mapint():
    return list(map(int, input().split()))


sys.setrecursionlimit(10**9)
N, M, S = mapint()
graph = [{} for _ in range(N)]
for _ in range(M):
    u, v, a, t = mapint()
    graph[u - 1][v - 1] = (a, t)
    graph[v - 1][u - 1] = (a, t)
change = [list(mapint()) for _ in range(N)]
from heapq import heappop, heappush

# time, silver, vertex
Q = [(0, min(2500, S), 0)]
dist = [[10**18] * 2501 for _ in range(N)]
dist[0][min(2500, S)] = 0
while Q:
    t, s, v = heappop(Q)
    rate, change_time = change[v]
    if s < 2500 and dist[v][min(2500, s + rate)] > t + change_time:
        dist[v][min(2500, s + rate)] = t + change_time
        heappush(Q, (t + change_time, min(2500, s + rate), v))
    for nx in list(graph[v].keys()):
        nx_s, nx_t = graph[v][nx]
        if nx_s <= s and dist[nx][s - nx_s] > t + nx_t:
            dist[nx][s - nx_s] = t + nx_t
            heappush(Q, (t + nx_t, s - nx_s, nx))
for i in range(1, N):
    print((min(dist[i])))

-S = min(S, N * 50) -query = [[[] for _ in range(N * 50 + 1)] for _ in range(N)] +graph = [{} for _ in range(N)] -    u, v, a, b = mapint() -    for coin in range(a, N * 50 + 1): -        query[u - 1][coin].append((v - 1, a, b)) -        query[v - 1][coin].append((u - 1, a, b)) -for i in range(N): -    c, d = mapint() -    for coin in range(N * 50 + 1): -        query[i][coin].append((i, -c, d)) -inf = 10**18 -dp = [[inf] * (N * 50 + 1) for _ in range(N)] -dp[0][0] = 0 -import heapq +    u, v, a, t = mapint() +    graph[u - 1][v - 1] = (a, t) +    graph[v - 1][u - 1] = (a, t) +change = [list(mapint()) for _ in range(N)] +from heapq import heappop, heappush -queue = [(0, 0, S)] -checked = [0] * N -cnt = 0 -while queue: -    t, now, coin = heapq.heappop(queue) -    if cnt == N: -        break -    if not checked[now]: -        checked[now] = 1 -        cnt += 1 -    qlis = query[now][coin] -    for nx, a, b in qlis: -        if 0 <= coin - a: -            coin = min(coin, N * 50 + a) -            if t + b < dp[nx][coin - a]: -                dp[nx][coin - a] = t + b -                heapq.heappush(queue, (t + b, nx, coin - a)) +# time, silver, vertex +Q = [(0, min(2500, S), 0)] +dist = [[10**18] * 2501 for _ in range(N)] +dist[0][min(2500, S)] = 0 +while Q: +    t, s, v = heappop(Q) +    rate, change_time = change[v] +    if s < 2500 and dist[v][min(2500, s + rate)] > t + change_time: +        dist[v][min(2500, s + rate)] = t + change_time +        heappush(Q, (t + change_time, min(2500, s + rate), v)) +    for nx in list(graph[v].keys()): +        nx_s, nx_t = graph[v][nx] +        if nx_s <= s and dist[nx][s - nx_s] > t + nx_t: +            dist[nx][s - nx_s] = t + nx_t +            heappush(Q, (t + nx_t, s - nx_s, nx)) -    print((min(dp[i]))) +    print((min(dist[i])))