from heapq import*

(n,m,s),*t=[list(map(int,t.split()))for t in open(0)]

*e,=eval('[],'*8**6)

for u,v,a,b in t[:m]:

    for i in range(2501-a):

        e[(i+a)*51+u]+=(b,i*51+v),

        e[(i+a)*51+v]+=(b,i*51+u),

for i,(c,d)in enumerate(t[m:],1):

    for j in range(2501-c):

        e[j*51+i]+=(d,(j+c)*51+i),

d=[10**18]*8**6

f=[1]*8**6

q=[(0,min(2500,s)*51+1)]

while q:

    c,v=heappop(q)

    if f[v]<1:continue

    d[v],f[v]=c,0

    for p,w in e[v]:

        if f[w]:heappush(q,(c+p,w))

for i in range(2,n+1):print((min(d[i::51])))
def main():

    from heapq import heappush,heappop

    (n,m,s),*t=[list(map(int,r.split()))for r in open(0)]

    e=[[]for _ in range(8**6)]

    for u,v,a,b in t[:m]:

        for i in range(2501-a):

            e[(i+a)*51+u]+=(b,i*51+v),

            e[(i+a)*51+v]+=(b,i*51+u),

    for i,(c,d)in enumerate(t[m:],1):

        for j in range(2501-c):

            e[j*51+i]+=(d,(j+c)*51+i),

    x=[10**18]*8**6

    f=[1]*8**6

    q=[(0,min(2500,s)*51+1)]

    while q:

        c,v=heappop(q)

        if f[v]<1:continue

        x[v],f[v]=c,0

        for p,w in e[v]:

            if f[w]:heappush(q,(c+p,w))

    for i in range(2,n+1):print((min(x[i::51])))

main()
from heapq import *

(n, m, s), *t = [list(map(int, t.split())) for t in open(0)]
(*e,) = eval("[]," * 8**6)
for u, v, a, b in t[:m]:
    for i in range(2501 - a):
        e[(i + a) * 51 + u] += ((b, i * 51 + v),)
        e[(i + a) * 51 + v] += ((b, i * 51 + u),)
for i, (c, d) in enumerate(t[m:], 1):
    for j in range(2501 - c):
        e[j * 51 + i] += ((d, (j + c) * 51 + i),)
d = [10**18] * 8**6
f = [1] * 8**6
q = [(0, min(2500, s) * 51 + 1)]
while q:
    c, v = heappop(q)
    if f[v] < 1:
        continue
    d[v], f[v] = c, 0
    for p, w in e[v]:
        if f[w]:
            heappush(q, (c + p, w))
for i in range(2, n + 1):
    print((min(d[i::51])))

def main():
    from heapq import heappush, heappop

    (n, m, s), *t = [list(map(int, r.split())) for r in open(0)]
    e = [[] for _ in range(8**6)]
    for u, v, a, b in t[:m]:
        for i in range(2501 - a):
            e[(i + a) * 51 + u] += ((b, i * 51 + v),)
            e[(i + a) * 51 + v] += ((b, i * 51 + u),)
    for i, (c, d) in enumerate(t[m:], 1):
        for j in range(2501 - c):
            e[j * 51 + i] += ((d, (j + c) * 51 + i),)
    x = [10**18] * 8**6
    f = [1] * 8**6
    q = [(0, min(2500, s) * 51 + 1)]
    while q:
        c, v = heappop(q)
        if f[v] < 1:
            continue
        x[v], f[v] = c, 0
        for p, w in e[v]:
            if f[w]:
                heappush(q, (c + p, w))
    for i in range(2, n + 1):
        print((min(x[i::51])))


main()

-from heapq import * +def main(): +    from heapq import heappush, heappop -(n, m, s), *t = [list(map(int, t.split())) for t in open(0)] -(*e,) = eval("[]," * 8**6) -for u, v, a, b in t[:m]: -    for i in range(2501 - a): -        e[(i + a) * 51 + u] += ((b, i * 51 + v),) -        e[(i + a) * 51 + v] += ((b, i * 51 + u),) -for i, (c, d) in enumerate(t[m:], 1): -    for j in range(2501 - c): -        e[j * 51 + i] += ((d, (j + c) * 51 + i),) -d = [10**18] * 8**6 -f = [1] * 8**6 -q = [(0, min(2500, s) * 51 + 1)] -while q: -    c, v = heappop(q) -    if f[v] < 1: -        continue -    d[v], f[v] = c, 0 -    for p, w in e[v]: -        if f[w]: -            heappush(q, (c + p, w)) -for i in range(2, n + 1): -    print((min(d[i::51]))) +    (n, m, s), *t = [list(map(int, r.split())) for r in open(0)] +    e = [[] for _ in range(8**6)] +    for u, v, a, b in t[:m]: +        for i in range(2501 - a): +            e[(i + a) * 51 + u] += ((b, i * 51 + v),) +            e[(i + a) * 51 + v] += ((b, i * 51 + u),) +    for i, (c, d) in enumerate(t[m:], 1): +        for j in range(2501 - c): +            e[j * 51 + i] += ((d, (j + c) * 51 + i),) +    x = [10**18] * 8**6 +    f = [1] * 8**6 +    q = [(0, min(2500, s) * 51 + 1)] +    while q: +        c, v = heappop(q) +        if f[v] < 1: +            continue +        x[v], f[v] = c, 0 +        for p, w in e[v]: +            if f[w]: +                heappush(q, (c + p, w)) +    for i in range(2, n + 1): +        print((min(x[i::51]))) + + +main()