#!/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 = map(int,input().split())
s0 = min(250,s0)
G = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u-=1;v-=1
  G[u].append((v,a,b))
  G[v].append((u,a,b))
kankin = [tuple(map(int,input().split())) for i in range(n)]

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


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*250 for i in range(n)]
    dist[s][s0]
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
      time,money,u = heapq.heappop(hq)
      if dist[u][money] < time: continue
      c,d = kankin[u]
      while money <= 250:
        for v,money1,time1 in g[u]:
          if not money >= money1: continue
          if dist[v][money-money1] > time + time1:
            dist[v][money-money1] = (time + time1)
            heapq.heappush(hq,(time + time1, money-money1,v))
        money += c; time += d

    return #!/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 = map(int,input().split())
s0 = min(50,s0)
G = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  u-=1;v-=1
  G[u].append((v,a,b))
  G[v].append((u,a,b))
kankin = [tuple(map(int,input().split())) for i in range(n)]

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


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*51 for i in range(n)]
    dist[s][s0]
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
      time,money,u = heapq.heappop(hq)
      if dist[u][money] < time: continue
      c,d = kankin[u]
      while money <= 50:
        for v,money1,time1 in g[u]:
          if not money >= money1: continue
          if dist[v][money-money1] > time + time1:
            dist[v][money-money1] = (time + time1)
            heapq.heappush(hq,(time + time1, money-money1,v))
        money += c; time += d

    return dist

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




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




### FIXED CODE ###

#!/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 = map(int,input().split())
s0 = min(2500,s0)
G = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = 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 = 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]))