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):

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)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from pprint import pprint
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, S = MAP()
graph = [[] for _ in range(N)]
for _ in range(M):
	U, V, A, B = MAP()
	graph[U-1].append((V-1, A, B))
	graph[V-1].append((U-1, A, B))

C, D = ZIP(N)

def Extdijkstra(E, start):
    global S
    N_d = len(E)
    M = 2500
    if S >= M: S = M-1
    dist = [[INF]*M for _ in range(N_d)]
    dist[start][S] = 0
    q = [(0, S, start)]

    while q:
        d, num, v = heappop(q)
        if num+C[v] < M and d+D[v] < dist[v][num+C[v]]:  
            dist[v][num+C[v]] = d+D[v]
            heappush(q, (d+D[v], num+C[v], v))
        for node, c, t in E[v]:
            if num >= c and d + t < dist[node][num-c]:
                dist[node][num-c] = d+t
                heappush(q, (d+t, num-c, node))
    return dist

d = Extdijkstra(graph, 0)
for i in range(1, N):
	print(min(d[i]))

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


import heapq
def dijkstra_heap(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))


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)

Solution (Python):

import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    
    
    
    
    
    
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin >= n_coin and state[n_node][coin-n_coin] > n_time + time:
                state[n_node][coin - n_coin] = n_time + time
                heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

Solution (Python):
import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] 
dist[0][s] = 0
q = [(0,s,0)] 
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    
 
for i in range(1,n):
    print(min(dist[i]))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n, m, s = LI()
    uvab = LIR(m)
    cd = LIR(n)
    dp = [[inf] * 2501 for i in range(n)]
    edg = [[] for i in range(n)]
    for u, v, a, b in uvab:
        edg[u - 1].append((v - 1, a, b))
        edg[v - 1].append((u - 1, a, b))
    for i, (c, d) in enumerate(cd):
        edg[i].append((i, -c, d))
    if s >= 2501:
        s = 2500
    q = [(0, 0, s)]
    dp[0][s] = 0
    time = 0
    while q:
        time, p, score = heappop(q)
        for e, a, b in edg[p]:
            timebuf = time
            if 0 <= score - a <= 2500:
                timebuf += b
                if dp[e][score - a] > timebuf:
                    dp[e][score - a] = timebuf
                    heappush(q, (timebuf, e, score - a))
    
    for i in range(1, n):
        print(min(dp[i]))

    return



if __name__ == '__main__':
    solve()

Solution (Python):
from heapq import heappop, heappush


def solve(nn, mm, ss, line_list, cd_list):
    if ss > 5000:
        ss = 5000
    g = dict()
    for i in range(1, nn + 1):
        for s in range(5001):
            g[i * 10000 + s] = dict()
            if s + cd_list[i - 1][0] < 5000:
                g[i * 10000 + s][i * 10000 + s + cd_list[i - 1][0]] = cd_list[i - 1][1]
            elif s < 5000:
                g[i * 10000 + s][i * 10000 + 5000] = cd_list[i - 1][1]
    for u, v, a, b in line_list:
        for s in range(a, 5001):
            g[u * 10000 + s][v * 10000 + s - a] = b
            g[v * 10000 + s][u * 10000 + s - a] = b

    
    
    d = [10 ** 18] * ((nn + 1) * 10000)
    d[10000 + ss] = 0
    h = []
    heappush(h, (0, 10000 + ss))
    while len(h) > 0:
        t, u = heappop(h)
        for v in g[u].keys():
            if t + g[u][v] < d[v]:
                d[v] = t + g[u][v]
                heappush(h, (t + g[u][v], v))

    res = []
    for i in range(2, nn + 1):
        res.append(min(d[i * 10000:(i + 1) * 10000]))
    
    return res


def main():
    n, m, s = map(int, input().split())
    line_list = [list(map(int, input().split())) for _ in range(m)]
    cd_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, m, s, line_list, cd_list)
    for r in res:
        print(r)


def test():
    assert solve(3, 2, 1, [[1, 2, 1, 2], [1, 3, 2, 4]], [[1, 11], [1, 2], [2, 5]]) == [2, 14]
    assert solve(
        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]]
    ) == [5, 5, 7]


if __name__ == "__main__":
    test()
    main()

Solution (Python):
def main():
    import heapq
    inf = 10**16
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*2501 for _ in [0]*n]
    h = [(0, 0, min(s, 2500))]  
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 2500)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()

Solution (Python):
import sys
from heapq import*
input = sys.stdin.readline
def main():
    N,M,S = map(int,input().split())
    edges = [[]for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        edges[u].append((v,a,b))
        edges[v].append((u,a,b))
    ex = [tuple(map(int,input().split()))for _ in range(N)]

    M = 2500
    dist = [[2**60]*M for _ in range(N)]
    if S >= M:S = M-1
    dist[0][S] = 0
    q = [(0,S,0)]
    while q:
        cost,sil,u = heappop(q)
        if dist[u][sil] < cost:continue
        if sil+ex[u][0] < M and cost+ex[u][1] < dist[u][sil+ex[u][0]]:
            dist[u][sil+ex[u][0]] = cost + ex[u][1]
            heappush(q,(dist[u][sil+ex[u][0]],sil+ex[u][0],u))
        for v,a,b in edges[u]:
            if sil >= a and cost+b < dist[v][sil-a]:
                dist[v][sil-a] = cost+b
                heappush(q,(dist[v][sil-a],sil-a,v))
    for t in range(1,N):
        print(min(dist[t]))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from heapq import*
input = sys.stdin.readline
def main():
    N,M,S = map(int,input().split())
    edges = [[]for _ in range(N)]
    d = {}
    A = 0
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        A = max(A,a)
        edges[u].append((v,a,b))
        edges[v].append((u,a,b))
    ex = [tuple(map(int,input().split()))for _ in range(N)]

    M = 2500
    dist = [[2**60]*M for _ in range(N)]
    prev = [-1]*N
    if S >= M:S = M-1
    dist[0][S] = 0
    q = [(0,S,0)]
    while q:
        cost,sil,u = heappop(q)
        if dist[u][sil] < cost:continue
        if sil+ex[u][0] < M and cost+ex[u][1] < dist[u][sil+ex[u][0]]:
            dist[u][sil+ex[u][0]] = cost + ex[u][1]
            heappush(q,(dist[u][sil+ex[u][0]],sil+ex[u][0],u))
        for v,a,b in edges[u]:
            if sil >= a and cost+b < dist[v][sil-a]:
                dist[v][sil-a] = cost+b
                heappush(q,(dist[v][sil-a],sil-a,v))
    for t in range(1,N):
        print(min(dist[t]))





if __name__ == "__main__":
    main()

Solution (Python):
INF=1000000000000000 
MAX=50*50 

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

dp=[[INF] * (MAX + 1) for _ in range(n)]

dp[0][min(MAX, s)] = 0
updated = True
while updated:
  updated = False
  for i in range(n):
    for j in range(MAX + 1):
      dest = min(MAX, j + c[i])
      if dp[i][j] + d[i] < dp[i][dest]:
        updated = True
        dp[i][dest] = dp[i][j] + d[i]
  for i in range(m):
    for j in range(a[i], MAX+1):
      
      if dp[u[i]][j] + b[i] < dp[v[i]][j - a[i]]:
        updated = True
        dp[v[i]][j - a[i]] = dp[u[i]][j] + b[i]
      
      if dp[v[i]][j] + b[i] < dp[u[i]][j - a[i]]:
        updated = True
        dp[u[i]][j - a[i]] = dp[v[i]][j] + b[i]
for i in range(1, n):
  print(min(dp[i]))

Solution (Python):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

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)]

AMAX = 50
NODE_MAX = AMAX * (n - 1)
N = (NODE_MAX + 1) * n

U = []
V = []
C = []

for u, v, a, b in uvab:
    u -= 1
    v -= 1
    u *= NODE_MAX + 1
    v *= NODE_MAX + 1
    for i in range(NODE_MAX + 1 - a):
        U.append(u + i + a)
        V.append(v + i)
        C.append(b)
        U.append(v + i + a)
        V.append(u + i)
        C.append(b)


for i, (c, d) in enumerate(cd):
    base = i * (NODE_MAX + 1)
    for j in range(NODE_MAX):
        nxt = base + min(j + c, NODE_MAX)
        frm = base + j
        U.append(frm)
        V.append(nxt)
        C.append(d)

g = csr_matrix((C, (U, V)), shape=(N, N))
dist = dijkstra(g, indices=min(s, NODE_MAX)).astype(int)
dist[dist < 0] = dist.max()
for i in range(1, n):
    base = i * (NODE_MAX + 1)
    ans = dist[base:base+NODE_MAX+1].min()
    print(ans)

Solution (Python):
n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))

def dijkstra(s,n):
    from heapq import heappush,heappop
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d
d=dijkstra(s*n,n*50*51)
for i in range(1,n):
    print(d[i])

Solution (Python):
import heapq
N,M,S = [int(i) for i in input().split()]
S = min(S,2500)
Train = [[] for p in range(N)]
for j in range(M):
    U,V,A,B = [int(hoge) for hoge in input().split()]
    Train[U-1].append((V-1,(A,B)))
    Train[V-1].append((U-1,(A,B)))

CD = [[int(hoge) for hoge in input().split()] for k in range(N)]

num = N*2501          
dist = [float('inf') for i in range(num)] 
prev = [float('inf') for i in range(num)] 
    
start = 0 * 2501 + S
dist[start] = 0 
q = []                  
heapq.heappush(q, (0, start)) 
while len(q) != 0:
    prov_cost, src = heapq.heappop(q) 
    
    
    if dist[src] < prov_cost:
        continue

    
    src_Point = src//2501
    src_Money = src%2501
    src_RyogaeM = CD[src_Point][0]
    src_RyogaeTime = CD[src_Point][1]

    RyogaeAfter = min(2500,src_Money + src_RyogaeM)
    RyogaeID = src - src_Money + RyogaeAfter
    cost = src_RyogaeTime

    if dist[RyogaeID] > dist[src] + cost:
        dist[RyogaeID] = dist[src] + cost
        heapq.heappush(q,(dist[RyogaeID],RyogaeID))

    for togo,trainfo in Train[src//2501]:
        cost = trainfo[1]
        fee = trainfo[0]
        dest = togo * 2501 + src_Money - fee
        if src_Money >= fee and dist[dest] > dist[src] + cost:
            dist[dest] = dist[src] + cost 
            heapq.heappush(q, (dist[dest], dest)) 
            prev[dest] = src                      

curpoint = 0
TheEnd = 2500
curmin = float("inf")
for point,d in enumerate(dist):
    if d < curmin:
        curmin = d
    if point == TheEnd:
        TheEnd += 2501
        if point > 2500:
            print(curmin)
        curmin = float("inf")

Solution (Python):
n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
s=s*n
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
d[s]=0
heappush(pq,(0,s))
while pq:
    dist,u = heappop(pq)
    for v,cost in edge[u]:
        if d[v]<=dist+cost:
            continue
        d[v]=dist+cost
        heappush(pq,(d[v],v))
for i in range(1,n):
    print(d[i])

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

AM = 50*50+1
INF = 10**15

N, M, S = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph[u-1].append((a, b, v-1))
    graph[v-1].append((a, b, u-1))
C = []
D = []
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)


dp = [[INF]*(AM+1) for _ in range(N)]
dp[0][min(AM, S)] = 0
q = [(0, min(AM, S), 0)]
while q:
    dis, cost, p = hp.heappop(q)
    if dp[p][cost] < dis:
        continue
    if 0 <= cost+C[p] <= AM and dp[p][cost+C[p]] > dp[p][cost]+D[p]:
        dp[p][cost+C[p]] = dp[p][cost] + D[p]
        hp.heappush(q, (dp[p][cost+C[p]], cost+C[p], p))
    for a, b, np in graph[p]:
        if 0 <= cost-a <= AM and dp[np][cost-a] > dp[p][cost] + b:
            dp[np][cost-a] = dp[p][cost]+b
            hp.heappush(q, (dp[np][cost-a], cost-a, np))

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

Solution (Python):
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)]

M = 50 * n + 1
s = min(s, M - 1)

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

import math
dp[0][s] = 0
c, d = cd[0][0], cd[0][1]
for jj in range(M):
    dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for u, v in [(u1, v1), (v1, u1)]:
            for j in range(M - a):
                tmp = dp[u][j + a] + b
                if tmp < dp[v][j]:
                    dp[v][j] = tmp
                    flag = True

            if flag:
                c, d = cd[v][0], cd[v][1]
                for jj in range(c, M):
                    tmp = dp[v][jj - c] + d
                    if tmp < dp[v][jj]:
                        dp[v][jj] = tmp

    if flag == False:
        break

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

Solution (Python):
import heapq

INF = 2**60

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

E = []
for i in range(N):
    E.append([])

for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    E[u-1].append((v-1, a, b))
    E[v-1].append((u-1, a, b))

C, D = [], []
for i in range(N):
    c, d = list(map(int, input().split()))
    C.append(c)
    D.append(d)



dist = []
for i in range(51):
    dist.append([])
    for j in range(2501):
        dist[i].append(INF)

dist[0][min(S, 2500)] = 0


a = []
heapq.heappush(a, (INF, INF, INF))
heapq.heappush(a, (0, 0, min(S, 2500)))

while True:
    t = heapq.heappop(a)
    at = t[1]
    if t[0] == INF:
        break
    if dist[at][t[2]] < t[0]:
        continue
    if t[2] != 2500:
        if dist[t[1]][min(t[2] + C[at], 2500)] > t[0] + D[at]:
            dist[t[1]][min(t[2] + C[at], 2500)] = t[0] + D[at]
            heapq.heappush(a, (t[0] + D[at], t[1], min(t[2] + C[at], 2500)))

    for v in E[at]:
        nat = v[0]
        nd = t[0] + v[2]
        nrest = t[2] - v[1]
        if t[2] == 2500:
            nrest = 2500
        if nrest < 0:
            continue
        if dist[nat][nrest] > nd:
            dist[nat][nrest] = nd
            heapq.heappush(a, (nd, nat, nrest))


ans = [INF] * N
for i in range(N):
    for j in range(2501):
        ans[i] = min(ans[i], dist[i][j])


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

Solution (Python):
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)]


import math

M = 50 * n + 1
s = min(s, M - 1)

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

dp[0][s] = 0
c, d = cd[0][0], cd[0][1]
for jj in range(M):
    dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for u, v in [(u1, v1), (v1, u1)]:
            for j in range(M - a):
                tmp = dp[u][j + a] + b
                if tmp < dp[v][j]:
                    dp[v][j] = tmp
                    flag = True

            c, d = cd[v][0], cd[v][1]
            for jj in range(c, M):
                tmp = dp[v][jj - c] + d
                if tmp < dp[v][jj]:
                    dp[v][jj] = tmp
                    flag = True

    if flag == False:
        break

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

Solution (Python):
n,m,s = map(int,input().split())
uvab = [list(map(int,input().split())) for i in range(m)]
cd = [list(map(int,input().split())) for i in range(n)]
graph = [[] for i in range((n+1)*2500+1)]
for u2,v2,a,b in uvab:
  for u,v in (u2,v2),(v2,u2):
    for i in range(u*2500,u*2500+2500):
      if i%2500 >= a:
        graph[i].append((i+(v-u)*2500-a,b))
for i in range(n):
  c,d = cd[i]
  for j in range((i+1)*2500,(i+2)*2500-1):
    graph[j].append((min((i+2)*2500-1,j+c),d))
import heapq as hq
start = 2500+min(s,2499)
dist = [10**18]*((n+1)*2500+1)
dist[start] = 0
q = [(0,start)]
hq.heapify(q)
while q:
  _,x = hq.heappop(q)
  for y,d in graph[x]:
    if dist[y] > dist[x]+d:
      dist[y] = dist[x]+d
      hq.heappush(q,(dist[y],y))
for i in range(2,n+1):
  print(min(dist[i*2500:(i+1)*2500]))

Solution (Python):
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = map(int,input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = map(int,input().split())
    
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in edge[i].items():
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print(min(ans[i*(A+1):i*(A+1)+A+1]))

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

INF = float('inf')  
maxMoney = 2502  


N, M, S = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    u, v, coin, tm = map(int, input().split())
    u, v = u-1, v-1
    adjL[u].append((v, coin, tm))
    adjL[v].append((u, coin, tm))
moneys, tms = [], []
for _ in range(N):
    money, tm = map(int, input().split())
    moneys.append(money)
    tms.append(tm)


def Dijkstra(adjList):
    numV = N * (maxMoney+1)
    numUsed = 0
    costss = [[INF]*(maxMoney+1) for _ in range(N)]
    costss[0][S] = 0
    PQ = []
    heappush(PQ, (0, 0, S))
    while PQ:
        cNow, vNow, moneyNow = heappop(PQ)
        if cNow > costss[vNow][moneyNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, coin, tm in adjList[vNow]:
            if moneyNow < coin: continue
            c2 = cNow + tm
            m2 = moneyNow - coin
            if c2 < costss[v2][m2]:
                costss[v2][m2] = c2
                heappush(PQ, (c2, v2, m2))
        c2 = cNow + tms[vNow]
        m2 = moneyNow + moneys[vNow]
        if m2 > maxMoney:
            m2 = maxMoney
        if c2 < costss[vNow][m2]:
            costss[vNow][m2] = c2
            heappush(PQ, (c2, vNow, m2))
    return costss

S = min(S, maxMoney)
costss = Dijkstra(adjL)



anss = [min(costss[t]) for t in range(1, N)]
print('\n'.join(map(str, anss)))

Solution (Python):
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    for i in range(a, k):
        X[u * k + i].append([v * k + i - a, b])
        X[v * k + i].append([u * k + i - a, b])

for i in range(N):
    c, d = map(int, input().split())
    for j in range(k - 1):
        X[i * k + j].append([i * k + min(j + c, k - 1), d])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D

D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")