Buggy python submission (verdict: Time Limit Exceeded):
N,M,S=map(int,input().split())
S=min(2500,S)

#O(ElogV)
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  d,used={},{}
  for v in vlist:
    d[v]=float("inf")
    used[v]=True
  d[s]=0
  used[s]=False
  
  edgelist = []
  for e in edge[s]:
    heapq.heappush(edgelist,e)
    
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:      
      if used[e[1]]:
        heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        
  return d

uvab_list=[]
for i in range(M):
  U,V,A,B=map(int,input().split())
  uvab_list.append((U,V,A,B))
  
cd_list=[]
for i in range(N):
  C,D=map(int,input().split())
  cd_list.append((C,D))
  
vlist=[]
for i in range(1,N+1):
  for j in range(2501):
    vlist.append((i,j))

edge={}
for U,V,A,B in uvab_list:
  for j in range(2501):
    if j-A>=0:
      if not (U,j) in edge:
        edge[(U,j)]=[]    
      edge[(U,j)].append((B,(V,j-A)))
      if not (V,j) in edge:
        edge[(V,j)]=[]
      edge[(V,j)].append((B,(U,j-A)))

for i in range(N):
  C,D=cd_list[i]
  for j in range(2501):
    if not (i+1,j) in edge:
      edge[(i+1,j)]=[]    
    jj=min(2500,j+C)    
    edge[(i+1,j)].append((D,(i+1,jj)))
    
n=len(vlist)
w=len(edge)
res=dijkstra_heap((1,S))
#print(res)

for i in range(2,N+1):
  min_i=float("inf")
  for j in range(2501):
    min_i=min(min_i,res[(i,j)])
    
  print(min_i)

Fixed submission:
N,M,S=map(int,input().split())
S=min(2500,S)

#O(ElogV)
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  d,used={},{}
  for v in vlist:
    d[v]=float("inf")
    used[v]=True
  d[s]=0
  used[s]=False
  
  edgelist = []
  for e in edge[s]:
    heapq.heappush(edgelist,e)
    
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:      
      if used[e[1]]:
        heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        
  return d

uvab_list=[]
for i in range(M):
  U,V,A,B=map(int,input().split())
  uvab_list.append((U,V,A,B))
  
cd_list=[]
for i in range(N):
  C,D=map(int,input().split())
  cd_list.append((C,D))
  
vlist=[]
for i in range(1,N+1):
  for j in range(2501):
    vlist.append((i,j))

edge={}
for U,V,A,B in uvab_list:
  for j in range(2501):
    if j-A>=0:
      if not (U,j) in edge:
        edge[(U,j)]=[]    
      edge[(U,j)].append((B,(V,j-A)))
      if not (V,j) in edge:
        edge[(V,j)]=[]
      edge[(V,j)].append((B,(U,j-A)))

for i in range(N):
  C,D=cd_list[i]
  for j in range(2501):
    if not (i+1,j) in edge:
      edge[(i+1,j)]=[]    
    jj=min(2500,j+C)    
    edge[(i+1,j)].append((D,(i+1,jj)))
    
n=len(vlist)
w=len(edge)
res=dijkstra_heap((1,S))
#print(res)

for i in range(2,N+1):
  min_i=float("inf")
  for j in range(2501):
    min_i=min(min_i,res[(i,j)])
    
  print(min_i)

Buggy python submission (verdict: Runtime Error):
N,M,S=map(int,input().split())

#O(ElogV)
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  #d = [float("inf")] * n  
  #used = [True] * n #True:未確定
  d,used={},{}
  for v in vlist:
    d[v]=float("inf")
    used[v]=True
  d[s]=0
  used[s]=False
  
  edgelist = []
  for e in edge[s]:
    heapq.heappush(edgelist,e)
    
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:      
      if used[e[1]]:
        heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        
  return d

uvab_list=[]
for i in range(M):
  U,V,A,B=map(int,input().split())
  uvab_list.append((U,V,A,B))
  
cd_list=[]
for i in range(N):
  C,D=map(int,input().split())
  cd_list.append((C,D))
  
vlist=[]
for i in range(1,N+1):
  for j in range(2501):
    vlist.append((i,j))

edge={}
for U,V,A,B in uvab_list:
  for j in range(2501):
    if j-A>=0:
      if not (U,j) in edge:
        edge[(U,j)]=[]    
      edge[(U,j)].append((B,(V,j-A)))
      if not (V,j) in edge:
        edge[(V,j)]=[]
      edge[(V,j)].append((B,(U,j-A)))

for i in range(N):
  C,D=cd_list[i]
  for j in range(2501):
    if not (i+1,j) in edge:
      edge[(i+1,j)]=[]    
    jj=min(2500,j+C)    
    edge[(i+1,j)].append((D,(i+1,jj)))
    
n=len(vlist)
w=len(edge)
res=dijkstra_heap((1,S))
#print(res)

for i in range(2,N+1):
  min_i=float("inf")
  for j in range(2501):
    min_i=min(min_i,res[(i,j)])
    
  print(min_i)

Fixed submission:
N,M,S=map(int,input().split())
S=min(2500,S)

#O(ElogV)
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  d,used={},{}
  for v in vlist:
    d[v]=float("inf")
    used[v]=True
  d[s]=0
  used[s]=False
  
  edgelist = []
  for e in edge[s]:
    heapq.heappush(edgelist,e)
    
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:      
      if used[e[1]]:
        heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        
  return d

uvab_list=[]
for i in range(M):
  U,V,A,B=map(int,input().split())
  uvab_list.append((U,V,A,B))
  
cd_list=[]
for i in range(N):
  C,D=map(int,input().split())
  cd_list.append((C,D))
  
vlist=[]
for i in range(1,N+1):
  for j in range(2501):
    vlist.append((i,j))

edge={}
for U,V,A,B in uvab_list:
  for j in range(2501):
    if j-A>=0:
      if not (U,j) in edge:
        edge[(U,j)]=[]    
      edge[(U,j)].append((B,(V,j-A)))
      if not (V,j) in edge:
        edge[(V,j)]=[]
      edge[(V,j)].append((B,(U,j-A)))

for i in range(N):
  C,D=cd_list[i]
  for j in range(2501):
    if not (i+1,j) in edge:
      edge[(i+1,j)]=[]    
    jj=min(2500,j+C)    
    edge[(i+1,j)].append((D,(i+1,jj)))
    
n=len(vlist)
w=len(edge)
res=dijkstra_heap((1,S))
#print(res)

for i in range(2,N+1):
  min_i=float("inf")
  for j in range(2501):
    min_i=min(min_i,res[(i,j)])
    
  print(min_i)