from heapq import heappop,heappush

inf = float("inf")



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



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

for _ in range(m):

    u,v,cost,time = list(map(int,input().split()))

    u -= 1

    v -= 1

    G[u].append((v,cost,time))

    G[v].append((u,cost,time))



for i in range(n):

    cost,time = list(map(int,input().split()))

    G[i].append((i,-cost,time))



# mint[i][j]

# 銀貨j枚を持って都市iに着くことができる最小時間

mint = [[inf]*2451 for _ in range(n)]



# color[i][j]

# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか

white = 0

black = 1

color = [[white]*2451 for _ in range(n)]



def dijkstra(u,s):

    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる

    s = min(s,2450)

    mint[u][s] = 0

    color[u][s] = black



    PQ = []

    heappush(PQ,(0,u,s))

    while PQ:

        # minv: PQ内の最小値

        # now: 今いる都市

        # nowcoins: 今持っている銀貨

        minv,now,nowcoins = heappop(PQ)

        color[now][nowcoins] = black

        

        # nxt: 次に行く都市

        # cost: 次の都市に行くのに使う銀貨

        # time: 次の都市に行くのにかかる時間

        # nxtcoins: 次の都市に行った段階で持っている銀貨

        for nxt,cost,time in G[now]:

            nxtcoins = min(nowcoins - cost,2450)

            if nxtcoins < 0: continue

            if color[nxt][nxtcoins]: continue

            if mint[nxt][nxtcoins] > minv + time:

                mint[nxt][nxtcoins] = minv + time

                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))



dijkstra(0,s)



# for i in range(n): print(mint[i])

# for i in range(n): print(color[i])

for i in range(1,n): print((min(mint[i])))
from heapq import heappop,heappush

inf = float("inf")



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



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

for _ in range(m):

    u,v,cost,time = list(map(int,input().split()))

    u -= 1

    v -= 1

    G[u].append((v,cost,time))

    G[v].append((u,cost,time))



for i in range(n):

    cost,time = list(map(int,input().split()))

    G[i].append((i,-cost,time))



# mint[i][j]

# 銀貨j枚を持って都市iに着くことができる最小時間

mint = [[inf]*2451 for _ in range(n)]



# color[i][j]

# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか

white = 0

black = 1

color = [[white]*2451 for _ in range(n)]



def dijkstra(u,s):

    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる

    s = min(s,2450)

    mint[u][s] = 0

    color[u][s] = black



    PQ = []

    heappush(PQ,(0,u,s))

    while PQ:

        # minv: PQ内の最小値

        # now: 今いる都市

        # nowcoins: 今持っている銀貨

        minv,now,nowcoins = heappop(PQ)

        color[now][nowcoins] = black

        # 最小時間じゃないなら無視

        if mint[now][nowcoins] < minv: continue

        

        # nxt: 次に行く都市

        # cost: 次の都市に行くのに使う銀貨

        # time: 次の都市に行くのにかかる時間

        # nxtcoins: 次の都市に行った段階で持っている銀貨

        for nxt,cost,time in G[now]:

            nxtcoins = min(nowcoins - cost,2450)

            if nxtcoins < 0: continue

            if color[nxt][nxtcoins]: continue

            if mint[nxt][nxtcoins] > minv + time:

                mint[nxt][nxtcoins] = minv + time

                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))



dijkstra(0,s)



# for i in range(n): print(mint[i])

# for i in range(n): print(color[i])

for i in range(1,n): print((min(mint[i])))
from heapq import heappop, heappush

inf = float("inf")
n, m, s = list(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, cost, time = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[u].append((v, cost, time))
    G[v].append((u, cost, time))
for i in range(n):
    cost, time = list(map(int, input().split()))
    G[i].append((i, -cost, time))
# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf] * 2451 for _ in range(n)]
# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white] * 2451 for _ in range(n)]


def dijkstra(u, s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s, 2450)
    mint[u][s] = 0
    color[u][s] = black
    PQ = []
    heappush(PQ, (0, u, s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv, now, nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt, cost, time in G[now]:
            nxtcoins = min(nowcoins - cost, 2450)
            if nxtcoins < 0:
                continue
            if color[nxt][nxtcoins]:
                continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ, (mint[nxt][nxtcoins], nxt, nxtcoins))


dijkstra(0, s)
# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1, n):
    print((min(mint[i])))

from heapq import heappop, heappush

inf = float("inf")
n, m, s = list(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, cost, time = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[u].append((v, cost, time))
    G[v].append((u, cost, time))
for i in range(n):
    cost, time = list(map(int, input().split()))
    G[i].append((i, -cost, time))
# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf] * 2451 for _ in range(n)]
# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white] * 2451 for _ in range(n)]


def dijkstra(u, s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s, 2450)
    mint[u][s] = 0
    color[u][s] = black
    PQ = []
    heappush(PQ, (0, u, s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv, now, nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        # 最小時間じゃないなら無視
        if mint[now][nowcoins] < minv:
            continue
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt, cost, time in G[now]:
            nxtcoins = min(nowcoins - cost, 2450)
            if nxtcoins < 0:
                continue
            if color[nxt][nxtcoins]:
                continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ, (mint[nxt][nxtcoins], nxt, nxtcoins))


dijkstra(0, s)
# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1, n):
    print((min(mint[i])))

+        # 最小時間じゃないなら無視 +        if mint[now][nowcoins] < minv: +            continue