import sys

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



import heapq

h = []

heapq.heapify(h)



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

a, b = [[None] * m for _ in range(2)]

c, d = [[None] * n for _ in range(2)]



ns = {u: [] for u in range(n)}

uv2e = {}

for i in range(m):

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

    ns[u-1].append(v-1)

    ns[v-1].append(u-1)

    uv2e[u-1,v-1] = i

    uv2e[v-1,u-1] = i

for i in range(n):

    c[i], d[i] = list(map(int, input().split()))



maxs = max(a)*(n-1)

s = min(s, maxs)

state = (0, 0, s) # (距離, ノード, 銀貨枚数)

ans = [[None] * (maxs+1) for _ in range(n)]

heapq.heappush(h, state)

count = 0

while h:

    count += 1

    dd, u, ss = heapq.heappop(h)

#     print(dd, u, ss)

    if ans[u][ss] is not None and ans[u][ss] <= dd:

        continue

    ans[u][ss] = dd

    

    # グラフの隣接点

    for v in ns[u]:

        e= uv2e[u,v]

        if ss<a[e] or ans[v][ss-a[e]] is not None:

            continue

        heapq.heappush(h, (dd + b[e], v, ss-a[e]))

    # 両替

    if ss+c[u] <= maxs:

        heapq.heappush(h, (dd + d[u], u, ss+c[u]))

    elif ss < maxs:

        heapq.heappush(h, (dd + d[u], u, maxs))



for item in ans[1:]:

    print((min(item)))

import sys

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

sys.setrecursionlimit(max(1000, 10**9))

write = lambda x: sys.stdout.write(x+"\n")





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

cd = [None]*n

from collections import defaultdict

ns = defaultdict(set)

nns = defaultdict(set)

uvab = [None]*m

for i in range(m):

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

    u -= 1

    v -= 1

    uvab[i] = (u,v,a,b)

    ns[u].add((a,b,v))

    ns[v].add((a,b,u))

for i in range(n):

    cd[i] = list(map(int, input().split()))



ms = max(item[2] for item in uvab)*(n-1)

for u in range(n):

    for ss in range(ms+1):

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

            if ss>=a:

                nns[u,ss].add((b, (v,ss-a)))

        c,d = cd[u]

        if ss+c<=ms:

            nns[u,ss].add((d, (u,ss+c)))

ns = nns

def dijkstra(start):

    import heapq

    vals = {}

    h = [(0, start)] # (距離, ノード番号)

    vals[start] = 0

    while h:

        val, u = heapq.heappop(h)

        for d, v in ns[u]:

            if v not in vals or vals[v]>val+d:

                vals[v] = val+d

                heapq.heappush(h, (vals[v], v))

    return vals

s = min(s, ms)

vals = dijkstra((0,s))

ans = [None]*(n-1)

for u in range(1,n):

    ans[u-1] = min(vals[u,s] for s in range(ms+1))

write("\n".join(map(str, ans)))
import sys

input = lambda: sys.stdin.readline().rstrip()
import heapq

h = []
heapq.heapify(h)
n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]
ns = {u: [] for u in range(n)}
uv2e = {}
for i in range(m):
    u, v, a[i], b[i] = list(map(int, input().split()))
    ns[u - 1].append(v - 1)
    ns[v - 1].append(u - 1)
    uv2e[u - 1, v - 1] = i
    uv2e[v - 1, u - 1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))
maxs = max(a) * (n - 1)
s = min(s, maxs)
state = (0, 0, s)  # (距離, ノード, 銀貨枚数)
ans = [[None] * (maxs + 1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)
    #     print(dd, u, ss)
    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    # グラフの隣接点
    for v in ns[u]:
        e = uv2e[u, v]
        if ss < a[e] or ans[v][ss - a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss - a[e]))
    # 両替
    if ss + c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss + c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))
for item in ans[1:]:
    print((min(item)))

import sys

input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x + "\n")
n, m, s = list(map(int, input().split()))
cd = [None] * n
from collections import defaultdict

ns = defaultdict(set)
nns = defaultdict(set)
uvab = [None] * m
for i in range(m):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    uvab[i] = (u, v, a, b)
    ns[u].add((a, b, v))
    ns[v].add((a, b, u))
for i in range(n):
    cd[i] = list(map(int, input().split()))
ms = max(item[2] for item in uvab) * (n - 1)
for u in range(n):
    for ss in range(ms + 1):
        for a, b, v in ns[u]:
            if ss >= a:
                nns[u, ss].add((b, (v, ss - a)))
        c, d = cd[u]
        if ss + c <= ms:
            nns[u, ss].add((d, (u, ss + c)))
ns = nns


def dijkstra(start):
    import heapq

    vals = {}
    h = [(0, start)]  # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v] > val + d:
                vals[v] = val + d
                heapq.heappush(h, (vals[v], v))
    return vals


s = min(s, ms)
vals = dijkstra((0, s))
ans = [None] * (n - 1)
for u in range(1, n):
    ans[u - 1] = min(vals[u, s] for s in range(ms + 1))
write("\n".join(map(str, ans)))

-import heapq +sys.setrecursionlimit(max(1000, 10**9)) +write = lambda x: sys.stdout.write(x + "\n") +n, m, s = list(map(int, input().split())) +cd = [None] * n +from collections import defaultdict -h = [] -heapq.heapify(h) -n, m, s = list(map(int, input().split())) -a, b = [[None] * m for _ in range(2)] -c, d = [[None] * n for _ in range(2)] -ns = {u: [] for u in range(n)} -uv2e = {} +ns = defaultdict(set) +nns = defaultdict(set) +uvab = [None] * m -    u, v, a[i], b[i] = list(map(int, input().split())) -    ns[u - 1].append(v - 1) -    ns[v - 1].append(u - 1) -    uv2e[u - 1, v - 1] = i -    uv2e[v - 1, u - 1] = i +    u, v, a, b = list(map(int, input().split())) +    u -= 1 +    v -= 1 +    uvab[i] = (u, v, a, b) +    ns[u].add((a, b, v)) +    ns[v].add((a, b, u)) -    c[i], d[i] = list(map(int, input().split())) -maxs = max(a) * (n - 1) -s = min(s, maxs) -state = (0, 0, s)  # (距離, ノード, 銀貨枚数) -ans = [[None] * (maxs + 1) for _ in range(n)] -heapq.heappush(h, state) -count = 0 -while h: -    count += 1 -    dd, u, ss = heapq.heappop(h) -    #     print(dd, u, ss) -    if ans[u][ss] is not None and ans[u][ss] <= dd: -        continue -    ans[u][ss] = dd -    # グラフの隣接点 -    for v in ns[u]: -        e = uv2e[u, v] -        if ss < a[e] or ans[v][ss - a[e]] is not None: -            continue -        heapq.heappush(h, (dd + b[e], v, ss - a[e])) -    # 両替 -    if ss + c[u] <= maxs: -        heapq.heappush(h, (dd + d[u], u, ss + c[u])) -    elif ss < maxs: -        heapq.heappush(h, (dd + d[u], u, maxs)) -for item in ans[1:]: -    print((min(item))) +    cd[i] = list(map(int, input().split())) +ms = max(item[2] for item in uvab) * (n - 1) +for u in range(n): +    for ss in range(ms + 1): +        for a, b, v in ns[u]: +            if ss >= a: +                nns[u, ss].add((b, (v, ss - a))) +        c, d = cd[u] +        if ss + c <= ms: +            nns[u, ss].add((d, (u, ss + c))) +ns = nns + + +def dijkstra(start): +    import heapq + +    vals = {} +    h = [(0, start)]  # (距離, ノード番号) +    vals[start] = 0 +    while h: +        val, u = heapq.heappop(h) +        for d, v in ns[u]: +            if v not in vals or vals[v] > val + d: +                vals[v] = val + d +                heapq.heappush(h, (vals[v], v)) +    return vals + + +s = min(s, ms) +vals = dijkstra((0, s)) +ans = [None] * (n - 1) +for u in range(1, n): +    ans[u - 1] = min(vals[u, s] for s in range(ms + 1)) +write("\n".join(map(str, ans)))