Problem:
 Score : 500 points    Problem Statement  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.      Constraints   2 \leq N \leq 50  N-1 \leq M \leq 100  0 \leq S \leq 10^9  1 \leq A_i \leq 50  1 \leq B_i,C_i,D_i \leq 10^9  1 \leq U_i < V_i \leq N  There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j) .  Each city t=2,...,N can be reached from City 1 with some number of railroads.  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  M  S  U_1  V_1  A_1  B_1  :  U_M  V_M  A_M  B_M  C_1  D_1  :  C_N  D_N       Output  For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t .        Sample Input 1 3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5      Sample Output 1 2
14  The railway network in this input is shown in the figure below.  In this figure, each city is labeled as follows:   The first line: the ID number i of the city ( i for City i )  The second line: C_i / D_i   Similarly, each railroad is labeled as follows:   The first line: the ID number i of the railroad ( i for the i -th railroad in input)  The second line: A_i / B_i    You can travel from City 1 to City 2 in 2 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 2 minutes.    You can travel from City 1 to City 3 in 14 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 2 minutes.  At the exchange counter in City 2 , exchange 3 gold coins for 3 silver coins in 6 minutes.  Use the 1 -st railroad to move from City 2 to City 1 in 2 minutes.  Use the 2 -nd railroad to move from City 1 to City 3 in 4 minutes.        Sample Input 2 4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4      Sample Output 2 5
5
7  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 4 in 7 minutes, as follows:   At the exchange counter in City 1 , exchange 2 gold coins for 6 silver coins in 2 minutes.  Use the 2 -nd railroad to move from City 1 to City 3 in 4 minutes.  Use the 4 -th railroad to move from City 3 to City 4 in 1 minutes.        Sample Input 3 6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1      Sample Output 3 1
9003
14606
16510
16576  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 6 in 16576 minutes, as follows:   Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.  At the exchange counter in City 2 , exchange 3 gold coins for 3 silver coins in 9000 minutes.  Use the 1 -st railroad to move from City 2 to City 1 in 1 minute.  Use the 2 -nd railroad to move from City 1 to City 3 in 1 minute.  At the exchange counter in City 3 , exchange 8 gold coins for 8 silver coins in 5600 minutes.  Use the 2 -nd railroad to move from City 3 to City 1 in 1 minute.  Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.  Use the 3 -rd railroad to move from City 2 to City 4 in 1 minute.  At the exchange counter in City 4 , exchange 19 gold coins for 19 silver coins in 1900 minutes.  Use the 3 -rd railroad to move from City 4 to City 2 in 1 minute.  Use the 1 -st railroad to move from City 2 to City 1 in 1 minute.  Use the 2 -nd railroad to move from City 1 to City 3 in 1 minute.  Use the 4 -th railroad to move from City 3 to City 5 in 1 minute.  At the exchange counter in City 5 , exchange 63 gold coins for 63 silver coins in 63 minutes.  Use the 4 -th railroad to move from City 5 to City 3 in 1 minute.  Use the 2 -nd railroad to move from City 3 to City 1 in 1 minute.  Use the 5 -th railroad to move from City 1 to City 6 in 1 minute.        Sample Input 4 4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7      Sample Output 4 1
3
5  The railway network in this input is shown in the figure below:        Sample Input 5 2 1 0
1 2 1 1
1 1000000000
1 1      Sample Output 5 1000000001  The railway network in this input is shown in the figure below:   You can travel from City 1 to City 2 in 1000000001 minutes, as follows:   At the exchange counter in City 1 , exchange 1 gold coin for 1 silver coin in 1000000000 minutes.  Use the 1 -st railroad to move from City 1 to City 2 in 1 minute.

Solution (Python):
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")



import heapq
def dijkstra_heap(G, si, sj, h, w):
    
    d = [[INF] * w for _ in range(h)]
    used = [[False] * w for _ in range(h)]
    d[si][sj] = 0
    used[si][sj] = True

    edgelist = []
    for edge in G[si][sj]:
        cost, i, j = edge[0], edge[1], edge[2]
        heapq.heappush(edgelist, [cost, i, j])
    
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        cost, i, j = minedge[0], minedge[1], minedge[2]
        
        if used[i][j]:
            continue
        d[i][j] = cost
        used[i][j] = True

        for edge in G[i][j]:
            cost, ni, nj = edge[0], edge[1], edge[2]
            if used[ni][nj]:
                continue
            heapq.heappush(edgelist, [cost + d[i][j], ni, nj])
    return d


def main():
    N, M, S = map(int, input().split())

    U = [0] * M
    V = [0] * M
    A = [0] * M
    B = [0] * M
    for i in range(M):
        U[i], V[i], A[i], B[i] = map(int, input().split())
        U[i] -= 1; V[i] -= 1
    
    L = max(A) * N
    G = [[[] for _ in range(L+1)] for _ in range(N)]
    for i in range(M):
        u, v, a, b = U[i], V[i], A[i], B[i]
        for money in range(L):
            if money - a >= 0:
                G[u][money].append([b, v, money - a])
                G[v][money].append([b, u, money - a])
    
    for station in range(N):
        c, d = map(int, input().split())
        for money in range(L):
            nmoney = money + c
            if nmoney > L:
                nmoney = L
            G[station][money].append([d, station, nmoney])
            G[station][nmoney].append([0, station, money])
    
    if S > L:
        S = L
    ans = dijkstra_heap(G, 0, S, N, L+1)
    for i in range(1, N):
        print(min(ans[i]))
    

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
import heapq
n,m,s=map(int,input().split())
s=min(s,2499)
E=[]
for _ in range(m):
  E.append(tuple(map(int,input().split())))
CD=[]
for _ in range(n):
  CD.append(tuple(map(int,input().split())))
nn=n*2500
edge=[[] for i in range(nn)]
for u,v,a,b in E:
  u-=1
  v-=1
  for i in range(a,2500):
    edge[u*2500+i].append(b*10**6+v*2500+i-a)
    edge[v*2500+i].append(b*10**6+u*2500+i-a)
for i in range(n):
  c,d=CD[i]
  for j in range(2500):
    if j+c<2500:
      edge[i*2500+j].append(d*10**6+i*2500+j+c)

def dijkstra_heap(s):
  d=[float("inf")]*nn
  used=[True]*nn
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d
D=dijkstra_heap(s)
for i in range(1,n):
  ans=D[i*2500]
  for j in range(1,2500):
    ans=min(ans,D[i*2500+j])
  print(ans)

Solution (Python):
import heapq

MAX = 2500

n, m, s = map(int, input().split())
s = min(s, MAX)


edge = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    edge[u-1].append([v-1, a, b])
    edge[v-1].append([u-1, a, b])
for i in range(n):
    c, d = map(int, input().split())
    edge[i].append([i, -c, d])


dp = [[float("inf")]*(MAX+1) for _ in range(n)]
dp[0][s] = 0


edgelist = [(0, 0, s)]

while edgelist:
    time, node, silver = heapq.heappop(edgelist)

    for to, silver_cost, time_cost in edge[node]:
        res_silver = min(silver - silver_cost, MAX)
        if res_silver < 0:
            continue
        
        dp_next_value = time + time_cost
        if dp[to][res_silver] <= dp_next_value:
            continue

        dp[to][res_silver] = dp_next_value
        heapq.heappush(edgelist, (dp_next_value, to, res_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

Solution (Python):


import sys
import heapq

INF = float('inf')


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX = max(A) * (N-1)
    S = min(S, MAX)

    G = [[] for _ in range(N)]
    for u, v, a, b in zip(U, V, A, B):
        G[u-1].append([v-1, [a, b]])
        G[v-1].append([u-1, [a, b]])

    dp = [[INF for _ in range(MAX + 1)] for _ in range(N)]
    dp[0][S] = 0

    Q = []
    heapq.heapify(Q)
    heapq.heappush(Q, [0, [0, S]])

    while len(Q) != 0:
        time, [v, s] = heapq.heappop(Q)
        if time > dp[v][s]:
            continue

        if s + C[v] <= MAX:
            ns = s + C[v]
            ntime = time + D[v]
            if dp[v][ns] > ntime:
                dp[v][ns] = ntime
                heapq.heappush(Q, [ntime, [v, ns]])

        for nv, [ns, ntime] in G[v]:
            if s < ns:
                continue
            ns = s - ns
            ntime += time
            if dp[nv][ns] > ntime:
                dp[nv][ns] = ntime
                heapq.heappush(Q, [ntime, [nv, ns]])

    ans = [min(dp[i]) for i in range(1, N)]
    return "\n".join(map(str, ans))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    S = int(next(tokens))  
    U = [int()] * (M)  
    V = [int()] * (M)  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  
    D = [int()] * (N)  
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, S, U, V, A, B, C, D))


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
from heapq import heappush, heappop

INF = 10 ** 18

N, M, S = map(int, input().split())
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a

def dijkstra(start, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[start][1] = 0
    heap = []
    heappush(heap, (0, (start, 1)))
    while heap:
        v, (i, j) = heappop(heap)
        for w, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > v + w:
                dist[ni][nj] = v + w
                heappush(heap, (dist[ni][nj], (ni, nj)))
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]

for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        graph[i][u].append((b, (i - a, v)))
        graph[i][v].append((b, (i - a, u)))

for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA):
        graph[i][j].append((d, (min(i + c, sumA), j)))

dist = dijkstra(min(S, sumA), graph)

for j in range(2, N + 1):
    answer = INF
    for i in range(sumA + 1):
        answer = min(dist[i][j], answer)
    print(answer)

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M, S = map(int, input().split())
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a


def dijkstra(s, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[s][1] = 0
    hp = []
    heappush(hp, (0, (s, 1)))
    while hp:
        
        t, (i, j) = heappop(hp)
        for dt, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > t + dt:
                dist[ni][nj] = t + dt
                heappush(hp, (dist[ni][nj], (ni, nj)))
    
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]




for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA + 1):
        graph[i][j].append((d, (min(i + c, sumA), j)))



for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        if i >= a:
            graph[i][u].append((b, (i - a, v)))
            graph[i][v].append((b, (i - a, u)))




dist = dijkstra(min(S, sumA), graph)

for j in range(2, N + 1):
    ans = INF
    for i in range(sumA + 1):
        ans = min(dist[i][j], ans)
    print(ans)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

INF = 10 ** 18

class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time

dp = []
h = []

def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))

def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)

    while h:
        
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)


n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]

es = [[] for i in range(n)]
max_s = 50 * (n-1)

for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))

dijkstra(n, es, cd, 0, min(max_s,s), max_s)

for i in range(1, n):
    print(min(dp[i]))

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

INF = 10 ** 18

class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time

dp = []
h = []

def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))

def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)

    while h:
        
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))

        
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)


n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]

es = [[] for i in range(n)]
max_s = 50 * (n-1)

for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))

dijkstra(n, es, cd, 0, min(max_s,s), max_s)

for i in range(1, n):
    print(min(dp[i]))

Solution (Python):
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, S = map(int, rl().split())
    init_s = min(2500, S)
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, rl().split())
        u, v = u - 1, v - 1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    C, D = [0] * N, [0] * N
    for i in range(N):
        C[i], D[i] = map(int, rl().split())
    
    costs = [[10 ** 18] * 2501 for _ in range(N)]
    costs[0][init_s] = 0
    
    que = [(0, 0, init_s)]
    while que:
        t, cur, s = heappop(que)
        self_roop_s = min(s + C[cur], 2500)
        self_roop_t = t + D[cur]
        if self_roop_t < costs[cur][self_roop_s]:
            costs[cur][self_roop_s] = self_roop_t
            heappush(que, (self_roop_t, cur, self_roop_s))
        for child, s_cost, t_cost in graph[cur]:
            if s < s_cost:
                continue
            nt = t + t_cost
            ns = s - s_cost
            if nt < costs[child][ns]:
                costs[child][ns] = nt
                heappush(que, (nt, child, ns))
    
    for costs_i in costs[1:]:
        print(min(costs_i))


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input =sys.stdin.readline
import heapq

def dijkstra(edge, start):
    n = len(edge)
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist

n, m, s = map(int, input().split())
G = [[] for _ in range(n)]
if s >= 2500:
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, b))
    G[v].append((u, b))
  L = dijkstra(G, 0)
else:
  for _ 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))
  CD = [list(map(int, input().split())) for _ in range(n)]
  edge = [[] for _ in range(n*2500)]
  for i in range(n):
    c, d = CD[i]
    for k in range(2500):
      for v, a, b in G[i]:
        if k >= a:
          edge[2500*i+k].append((2500*v+(k-a), b))
      if k+c < 2500:
        edge[2500*i+k].append((2500*i+(k+c), d))
  dist = dijkstra(edge, s)
  L = [0]*n
  for i in range(n):
    L[i] = min(dist[2500*i:2500*(i+1)])
print(*L[1:], sep="\n")

Solution (Python):
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines



def main():
    N,M,S = map(int, readline().split())

    E = [[] for _ in range(N+1)]
    for _ in range(M):
        u,v,a,b = map(int, readline().split())
        E[u].append((v, a, b))
        E[v].append((u, a, b))

    cd = map(int, read().split())
    CD = []
    for c, d in zip(*[iter(cd)]*2):
        CD.append((c, d))

    
    
    if S > 2500:
        S = 2500 - 1
    INF = 10**15
    d = [[INF] * 2500 for _ in range(N+1)]
    d[1][S] = 0

    Q = []
    heappush(Q, (0, S, 1))  
    
    while Q:
        time, s, u = heappop(Q)
        if time > d[u][s]:
            continue
        
        c_u, d_u = CD[u-1]
        if s + c_u < 2500 and time + d_u < d[u][s + c_u]:
            d[u][s + c_u] = time + d_u
            heappush(Q, (time + d_u, s + c_u, u))
        
        for v, a, b in E[u]:
            if s >= a and time + b < d[v][s - a]:
                d[v][s - a] = time + b
                heappush(Q, (time + b, s - a, v))

    for i in range(2,N+1):
        print(min(d[i]))


if __name__ == "__main__":
    main()

Solution (Python):
n, m, s = map(int, input().split())
rail = [[] for _ in range(n)]
fare = [[] for _ in range(n)]
time = [[] for _ in range(n)]
rate = []
TIME = []
for _ in range(m):
    i, j, k, l = map(int, input().split())
    i -= 1
    j -= 1
    rail[i].append(j)
    rail[j].append(i)
    fare[i].append(k)
    fare[j].append(k)
    time[i].append(l)
    time[j].append(l)
for _ in range(n):
    i, j = map(int, input().split())
    rate.append(i)
    TIME.append(j)
    


limit = [max(i) for i in fare]
limit = max(limit) * n
if s >= limit:
    s = limit - 1


dp = [[float('inf')] * limit for _ in range(n)]


import heapq
candidate = [(0, 0, s)]
heapq.heapify(candidate)

ans = [-1] * n
todo = n

while todo > 0:
    i, j, k = heapq.heappop(candidate)
    if dp[j][k] != float('inf'):
        continue
    dp[j][k] = i
    if ans[j] == -1:
        ans[j] = i
        todo -= 1

    
    for l in range(len(rail[j])):
        if fare[j][l] <= k and dp[rail[j][l]][k - fare[j][l]] == float('inf'):
            heapq.heappush(candidate, (i + time[j][l], rail[j][l], k - fare[j][l]))
    
    
    if k < limit - 1:
        heapq.heappush(candidate, (i + TIME[j], j, min([k + rate[j], limit - 1])))

for i in range(1, n):
    print(ans[i])

Solution (Python):
n, m, s = map(int, input().split())
rail = [[] for _ in range(n)]
fare = [[] for _ in range(n)]
time = [[] for _ in range(n)]
rate = []
TIME = []
for _ in range(m):
    i, j, k, l = map(int, input().split())
    i -= 1
    j -= 1
    rail[i].append(j)
    rail[j].append(i)
    fare[i].append(k)
    fare[j].append(k)
    time[i].append(l)
    time[j].append(l)
for _ in range(n):
    i, j = map(int, input().split())
    rate.append(i)
    TIME.append(j)
    


limit = [max(i) for i in fare]
limit = max(limit) * n
if s >= limit:
    s = limit - 1


dp = [[float('inf')] * limit for _ in range(n)]


import heapq
candidate = [(0, 0, s)]
heapq.heapify(candidate)

ans = [-1] * n
todo = n

while todo > 0:
    i, j, k = heapq.heappop(candidate)
    if dp[j][k] != float('inf'):
        continue
    dp[j][k] = i
    if ans[j] == -1:
        ans[j] = i
        todo -= 1

    
    for l in range(len(rail[j])):
        if fare[j][l] <= k and dp[rail[j][l]][k - fare[j][l]] == float('inf'):
            heapq.heappush(candidate, (i + time[j][l], rail[j][l], k - fare[j][l]))
    
    
    if k < limit - 1:
        heapq.heappush(candidate, (i + TIME[j], j, min([k + rate[j], limit - 1])))

for i in range(1, n):
    print(ans[i])

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline


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

row = []    
col = []    
data = []

for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for i in range(a, 2501):
        row.append(N * i + u)
        col.append(N * (i - a) + v)
        data.append(b)
        row.append(N * i + v)
        col.append(N * (i - a) + u)
        data.append(b)

for u in range(N):
    c, d = map(int, input().split())
    for i in range(1, c):
        row.append(N * (2500 - i) + u)
        col.append(N * 2500 + u)
        data.append(d)
    for i in range(c, 2501):
        row.append(N * (i - c) + u)
        col.append(N * i + u)
        data.append(d)

graph = csr_matrix((data, (row, col)), shape = (2501*N, 2501*N))

times = dijkstra(graph, directed  = True, indices = N * S)

for end in range(1, N):
    print(int(min(times[N * i + end] for i in range(2501))))

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) 
        v = collections.defaultdict(bool) 
        while len(q):
            
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: 
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        """
        Parameters
        ----------
        start:int
            start node
        goal:int
            goal node

        Return
        ----------
        ShortestPath:list(int)
            shortest path
        """
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

n, m, s = inpl()
LIMIT_SILVER = 2500
s=min(s,LIMIT_SILVER-1)
graph = Dijkstra()
for i in range(m):
    u,v,a,b = inpl()
    for j in range(a,LIMIT_SILVER):
        graph.add((u,j), (v,j-a), b, directed=True)
        graph.add((v,j), (u,j-a), b, directed=True)
for i in range(n):
    c,d = inpl()
    for j in range(c,LIMIT_SILVER):
        graph.add((i + 1, j - c), (i + 1, j), d, directed=True)

costs,_ = graph.Dijkstra_search((1,s))

for i in range(2, n + 1):
    ans=INF
    for j in range(2500):
        ans = min(ans, costs[(i, j)])
    print(ans)

Solution (Python):
from heapq import *
import sys
input = sys.stdin.buffer.readline
n, m, s = map(int, input().split())
lim = 2510
di = [[float("inf")] * lim for _ in range(n)]
di[0][min(s,lim-1)] = 0
con = [[] for _ in range(n)]
for _ in range(m):
	u, v, a, b = map(int, input().split())
	con[u - 1].append((v - 1, a, b))
	con[v - 1].append((u - 1, a, b))
q = [(0, min(s,lim-1), 0)]
cd = [list(map(int, input().split())) for _ in range(n)]
while q:
	time, have, cur = heappop(q)
	if di[cur][have] < time:
		continue
	c, d = cd[cur]
	if have + c < lim and di[cur][have + c] > time + d:
		di[cur][have + c] = time + d
		heappush(q, (time + d, have + c, cur))
	for nxt, dh, dt in con[cur]:
		if have >= dh and di[nxt][have - dh] > time + dt:
			di[nxt][have - dh] = time + dt
			heappush(q, (time + dt, have - dh, nxt))
for p in di[1:]:
	print(min(p))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    inf = 10**17
    

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    
    edge = [[] for _ in range(n)] 
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            for i in range(ng, -1, -1):
                if dp[nv][i] > t+b:
                    dp[nv][i] = t+b
                    f = 1
                else:
                    break
            else:
                heappush(hq, (t+b, ng, nv))
            if i != ng:
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    inf = 10**17
    

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    
    edge = [[] for _ in range(n)] 
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            f = 0
            for i in range(ng, -1, -1):
                if dp[nv][i] > t+b:
                    dp[nv][i] = t+b
                    f = 1
                else:
                    break
            if f:
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    inf = 10**17
    

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    
    edge = [[] for _ in range(n)] 
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            if dp[nv][ng] > t+b:
                dp[nv][ng] = t+b
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()