### BUGGY CODE ###

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict
import heapq
n,m,s = inm()
aas = []
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
    aas.append(aa)
maxa = max(aas)
s = min(s,(maxa+1)*n-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

#dst2 = defaultdict(dict)
dst2 = {}
for u in range(1,n+1):
    for p in range((maxa+1)*n-c[u]):
        dst2[(u,p)] = {(u,p+c[u]) : d[u]}
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range(m,(maxa+1)*n):
            if (u,p) not in dst2:
                dst2[(u,p)] = {}
            dst2[(u,p)][(v,p-m)] = t

if DBG:
    print("dst2)")
    for z in dst2:
        printn(str(z)+':')
        ddprint(dst2[z])
cost = {}
for z in dst2:
    cost[z] = BIG
q = [(0,1,s)]
while len(q)>0:
    dd,u,p = heapq.heappop(q)
    if cost[(u,p)]<=dd:
        continue
    cost[(u,p)] = dd
    for v,r in dst2[(u,p)]:
        heapq.heappush(q,(dd+dst2[(u,p)][(v,r)], v,r))

if DBG:
    print("cost)")
    for z in cost:
        printn(str(z)+':')
        ddprint(cost[z])
ans = [BIG]*(n+1)
for u,p in cost:
    ans[u] = min(ans[u], cost[(u,p)])
for i in range(2,n+1):
    print(ans[i])


### FIXED CODE ###

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict
import heapq
n,m,s = inm()
ST = 51*(n+1)
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
s = min(s,ST-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

dst2 = [[] for i in range((n+1)*ST)]
for u in range(1,n+1):
    for p in range(ST-c[u]):
        dst2[u*ST+p].append((u*ST+p+c[u], d[u]))
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range(m,ST):
            dst2[u*ST+p].append((v*ST+p-m,t))

if DBG:
    print("dst2)")
    for u,p in [(1,50),(2,50),(1,3)]:
        #z,pp = dst2[u*ST+p]
        ddprint("u {u} p {p} d2 {dst2[u*ST+p]}")
        for z in dst2[u*ST+p]:
            ddprint("v {z[0]//ST} q {z[0]%ST} t {z[1]}")

cost = [BIG]*((n+1)*ST)
q = [(0,1*ST+s)]
while len(q)>0:
    dd,u = heapq.heappop(q)
    if cost[u]<=dd:
        continue
    cost[u] = dd
    for v,t in dst2[u]:
        heapq.heappush(q,(dd+t, v))

if DBG:
    print("cost) ST {ST} s {s}")
    for u,p in [(2,204),(3,154),(4,154)]:
        ddprint("u {u} p {p} suf {u*ST+p} cost {cost[u*ST+p]}")

ddprint(cost)
ans = [BIG]*(n+1)
for i in range(2,n+1):
    ans[i] = min(cost[i*ST:(i+1)*ST])
    #ddprint(f"i {i} i*ST {i*ST}")
    ddprint(cost[i*ST:(i+1)*ST])
for i in range(2,n+1):
    print(ans[i])