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 scipy.sparse import*

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

R,C=[],[]

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

    for i in range(2501-a):

        R+=(i+a)*51+u,(i+a)*51+v

        C+=i*51+v,i*51+u

        D+=b,b

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

    for j in range(2501-c):

        R+=j*51+i,

        C+=(j+c)*51+i,

        D+=d,

d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)

for i in range(2,n+1):print((int(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 scipy.sparse import *

(n, m, s, *D), *t = [list(map(int, t.split())) for t in open(0)]
R, C = [], []
for u, v, a, b in t[:m]:
    for i in range(2501 - a):
        R += (i + a) * 51 + u, (i + a) * 51 + v
        C += i * 51 + v, i * 51 + u
        D += b, b
for i, (c, d) in enumerate(t[m:], 1):
    for j in range(2501 - c):
        R += (j * 51 + i,)
        C += ((j + c) * 51 + i,)
        D += (d,)
d = csgraph.dijkstra(csr_matrix((D, (R, C)), [8**6] * 2), 1, min(2500, s) * 51 + 1)
for i in range(2, n + 1):
    print((int(min(d[i::51]))))

-def main(): -    from heapq import heappush, heappop +from scipy.sparse import * -    (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() +(n, m, s, *D), *t = [list(map(int, t.split())) for t in open(0)] +R, C = [], [] +for u, v, a, b in t[:m]: +    for i in range(2501 - a): +        R += (i + a) * 51 + u, (i + a) * 51 + v +        C += i * 51 + v, i * 51 + u +        D += b, b +for i, (c, d) in enumerate(t[m:], 1): +    for j in range(2501 - c): +        R += (j * 51 + i,) +        C += ((j + c) * 51 + i,) +        D += (d,) +d = csgraph.dijkstra(csr_matrix((D, (R, C)), [8**6] * 2), 1, min(2500, s) * 51 + 1) +for i in range(2, n + 1): +    print((int(min(d[i::51]))))