Problem: There are N cities numbered 1 to N, connected by M railroads.  You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.  The i-th railroad connects City U_i and City V_i bidirectionally, and a one- way trip costs A_i silver coins and takes B_i minutes. You cannot use gold coins to pay the fare.  There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin. The transaction takes D_i minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.  For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Submission attempts (in order):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*n
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) 
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(N-1):
  print(ab[i][1])

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*N
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) 
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(1,N):
  print(ab[i][1])

Verdicts: Runtime Error

Accepted