#!/usr/bin/env python3

import sys, math, itertools, collections, bisect, heapq

input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')

inf = float('inf') ;mod = 10**9+7

mans = inf ;ans = 0 ;count = 0 ;pro = 1



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

s0 = min(2500,s0)

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

for i in range(m):

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

  u-=1;v-=1

  G[u].append((v,-a,b))

  G[v].append((u,-a,b))

for i in range(n):

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

  G[i].append((i,c,d))



def ceil(x,y):

  return (x-1)//y+1





def dijktra(g,s):

    n=len(g)

    dist = [[inf]*2501 for i in range(n)]

    dist[s][s0] = 0

    hq=[]

    heapq.heappush(hq,(0,s0,s))

    while hq:

        time,money,u = heapq.heappop(hq)

        if dist[u][money] < time: continue

        for v,money1,time1 in g[u]:

          M = min(2500,money+money1)

          if not M >= 0: continue

          if dist[v][M] > time + time1:

            dist[v][M] = (time + time1)

            heapq.heappush(hq,(time + time1, M,v))

    return dist



dist = dijktra(G,0)

# print(dist)

for i in range(1,n):

  print((min(dist[i])))







#!/usr/bin/env python3

import sys, math, itertools, collections, bisect, heapq

input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')

inf = float('inf') ;mod = 10**9+7

mans = inf ;ans = 0 ;count = 0 ;pro = 1



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

s0 = min(2500,s0)

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

for i in range(m):

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

  u-=1;v-=1

  G[u].append((v,-a,b))

  G[v].append((u,-a,b))

for i in range(n):

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

  G[i].append((i,c,d))



def dijktra(g,s):

    n=len(g)

    dist = [[inf]*2501 for i in range(n)]

    dist[s][s0] = 0

    hq=[]

    heapq.heappush(hq,(0,s0,s))

    while hq:

        time,money,u = heapq.heappop(hq)

        if dist[u][money] < time: continue

        for v,money1,time1 in g[u]:

          M = min(2500,money+money1)

          if not M >= 0: continue

          if dist[v][M] > time + time1:

            dist[v][M] = (time + time1)

            heapq.heappush(hq,(time + time1, M,v))

    return dist



dist = dijktra(G,0)

for i in range(1,n):

  print((min(dist[i])))
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq

input = lambda: sys.stdin.buffer.readline().rstrip().decode("utf-8")
inf = float("inf")
mod = 10**9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n, m, s0 = list(map(int, input().split()))
s0 = min(2500, s0)
G = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[u].append((v, -a, b))
    G[v].append((u, -a, b))
for i in range(n):
    c, d = list(map(int, input().split()))
    G[i].append((i, c, d))


def ceil(x, y):
    return (x - 1) // y + 1


def dijktra(g, s):
    n = len(g)
    dist = [[inf] * 2501 for i in range(n)]
    dist[s][s0] = 0
    hq = []
    heapq.heappush(hq, (0, s0, s))
    while hq:
        time, money, u = heapq.heappop(hq)
        if dist[u][money] < time:
            continue
        for v, money1, time1 in g[u]:
            M = min(2500, money + money1)
            if not M >= 0:
                continue
            if dist[v][M] > time + time1:
                dist[v][M] = time + time1
                heapq.heappush(hq, (time + time1, M, v))
    return dist


dist = dijktra(G, 0)
# print(dist)
for i in range(1, n):
    print((min(dist[i])))

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq

input = lambda: sys.stdin.buffer.readline().rstrip().decode("utf-8")
inf = float("inf")
mod = 10**9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n, m, s0 = list(map(int, input().split()))
s0 = min(2500, s0)
G = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[u].append((v, -a, b))
    G[v].append((u, -a, b))
for i in range(n):
    c, d = list(map(int, input().split()))
    G[i].append((i, c, d))


def dijktra(g, s):
    n = len(g)
    dist = [[inf] * 2501 for i in range(n)]
    dist[s][s0] = 0
    hq = []
    heapq.heappush(hq, (0, s0, s))
    while hq:
        time, money, u = heapq.heappop(hq)
        if dist[u][money] < time:
            continue
        for v, money1, time1 in g[u]:
            M = min(2500, money + money1)
            if not M >= 0:
                continue
            if dist[v][M] > time + time1:
                dist[v][M] = time + time1
                heapq.heappush(hq, (time + time1, M, v))
    return dist


dist = dijktra(G, 0)
for i in range(1, n):
    print((min(dist[i])))

-def ceil(x, y): -    return (x - 1) // y + 1 - - -# print(dist)