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
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,S=map(int,input().split())
    
    X=2500
    edge=[[] for _ in range(N*X)]
    for _ in range(M):
        U,V,A,B=map(int,input().split())
        U-=1
        V-=1
        for i in range(A,X):
            edge[U*X+i].append((B,V*X+i-A))
            edge[V*X+i].append((B,U*X+i-A))
    for i in range(N):
        C,D=map(int,input().split())
        for j in range(X-C):
            edge[i*X+j].append((D,i*X+j+C))

    from heapq import heappop,heappush
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    
    d=dijkstra(min(S,X-1),N*X,edge)
    for i in range(1,N):
        print(min(d[i*X:(i+1)*X]))

if __name__ == '__main__':
    main()

Solution (Python):
n,m,s=map(int,input().split())



s=min(s,2500)



edge=[[[] for i in range(50*50+1)] for i in range(n)]



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


for i in range(n):
    c,d=map(int,input().split())
      
    
    
    
    for j in range(2500):
        if j+c>=2500:
            edge[i][j].append((i,2500,d))
        elif j+c<2500:
            edge[i][j].append((i,j+c,d))
        
from heapq import heappush,heappop,heapify


d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]


d[0][s]=0

pq = []
heappush(pq,(0,0,s))

while len(pq):
    
    _,u,g = heappop(pq)
    
    
    
    
    for tuple in edge[u][g]:
        if d[tuple[0]][tuple[1]]>d[u][g]+tuple[2]:
            d[tuple[0]][tuple[1]]=d[u][g]+tuple[2]
            heappush(pq,[d[u][g]+tuple[2],tuple[0],tuple[1]])
        


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

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

MAX_MONEY = 2500
INF = float("inf")
n, m, s = map(int, input().split())
s = min(s, MAX_MONEY)
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1; v -= 1
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))
cd = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[INF] * (MAX_MONEY+10) for _ in range(n)]
dp[0][s] = 0

q = [(0, 0, s)]
while q:
    dist, v, money = heappop(q)
    if dp[v][money] < dist: continue
    for nv, fare, cost in graph[v]:
        nm = money - fare
        if nm < 0: continue
        if dp[nv][nm] > dp[v][money] + cost:
            dp[nv][nm] = dp[v][money] + cost
            heappush(q, (dp[nv][nm], nv, nm))
    
    nm = min(money+cd[v][0], MAX_MONEY)
    if dp[v][nm] > dp[v][money] + cd[v][1]:
        dp[v][nm] = dp[v][money] + cd[v][1]
        heappush(q, (dp[v][nm], v, nm))

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

Solution (Python):
from heapq import *

def dijkstra(sta):
    dist = [10**18]*(N*2510)
    dist[sta] = 0
    pq = []
    heappush(pq, (dist[sta], sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

N, M, S = map(int, input().split())
serial = [[0]*2510 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(2510):
        serial[i][j] = c
        c += 1

G = [[] for _ in range(N*2510)]

for _ in range(M):
    U, V, A, B = map(int, input().split())
    U -= 1
    V -= 1
    
    for i in range(A, 2510):
        G[serial[U][i]].append((serial[V][i-A], B))
        G[serial[V][i]].append((serial[U][i-A], B))

for v in range(N):
    C, D = map(int, input().split())
    
    for i in range(2510):
        if i+C>=2510:
            break
        
        G[serial[v][i]].append((serial[v][i+C], D))

dist = dijkstra(serial[0][min(S, 2509)])

for i in range(1, N):
    ans = 10**18
    
    for j in range(2510):
        ans = min(ans, dist[serial[i][j]])
    
    print(ans)

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)]
chg=10**5

from collections import defaultdict
link = defaultdict(list)
for node in range(n):
    cmai,dmin = cd[node]

    for frm in range(2600):
        link[node*chg + frm].append([node*chg + frm+cmai, dmin])

for i in range(m):
    u,v,a,b = uvab[i]
    u-=1
    v-=1
    for sil in range(2600):
        link[u*chg + sil+a].append([v*chg + sil,b])
        link[v*chg + sil+a].append([u*chg + sil,b])

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
def dks(g,start):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

f_sil = min(s,2555)
res=dks(link,f_sil)

for node in range(1,n):
    ans=float("inf")
    for sil in range(2600):
        ans=min(ans,res[node*chg + sil])
    print(ans)

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

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())
    Us[i] -= 1
    Vs[i] -= 1


V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

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

if S > Ns:
    S = Ns


for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    
    for i in range(Ns+1): 
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            
            row.append( V[(u,ns_s) ])
            col.append( V[(v,ns_g)] )
            data.append( b )
            
            row.append( V[(v,ns_s) ])
            col.append( V[(u,ns_g)] )
            data.append( b )



for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): 
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        row.append( V[(i,ns_s) ])
        col.append( V[(i,ns_g)] )
        data.append( d )

graph=coo_matrix((data, (row, col)), shape=(Nv,Nv))

s=V[(0,S)]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices = s)

for i in range(1,N):
    ans = min([dist_matrix[i*(Ns+1)+v] for v in range(Ns+1)])
    print(int(ans))

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N,M,S=map(int,input().split())
UVAB=[list(map(int,input().split())) for i in range(M)]
CD=[[0,0]]+[list(map(int,input().split())) for i in range(N)]
data=[defaultdict(list) for i in range(N+1)]

for u,v,a,b in UVAB:
    data[u][v]=[a,b]
    data[v][u]=[a,b]
idel_max=10**18
visited=[[idel_max for i in range(2501)] for n in range(N+1)]
visited2=[[0 for i in range(2501)] for n in range(N+1)]
stack=[]
t=0
c,d=CD[1]
flag=0
s=min(S,2500)
"""while not flag:
    if s>2500:
        s=2500
        flag=1
    visited[1][s]=t
    stack.append([t,s,1])
    t+=d
    s+=c"""

stack=[[t,s,1]]
visited[1][s]=t
while stack:
    
    
    
    t,s,q=heappop(stack)
    c,d=CD[q]
    flag=0
    if not visited2[q][s]:
        visited2[q][s]=1
        if s<2500:
            _s=min(s+c,2500)
            _t=t+d

            if _t<visited[q][_s]:
                
                visited[q][_s]=_t
                heappush(stack,[_t,_s,q])

        for p in data[q]:
            a,b=data[q][p]
            _s=s-a
            if _s>=0:
                _t=t+b
                if _t<visited[p][_s]:
                    visited[p][_s]=_t
                    heappush(stack,[_t,_s,p])

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

Solution (Python):
from heapq import heappop, heappush

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

INF = float('inf')
def dijkstra(s,n,g): 
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

def newv(v,s):
  return v*2500+s

s = min(s,2499)
e2 = [[] for _ in range(n*2500)]
for u in range(n):
  for j in range(2500):
    if j+c[u] < 2500:
      e2[newv(u,j)].append((newv(u,j+c[u]),d[u]))
    
    for v,a,b in e[u]:
      if j >= a:
        e2[newv(u,j)].append((newv(v,j-a),b))

l = dijkstra(newv(0,s),n*2500,e2)
for i in range(1,n):
  ans = INF
  for j in range(2500):
    ans = min(l[newv(i,j)],ans)
  print(ans)

Solution (Python):
from heapq import heappop, heappush

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

INF = float('inf')
def dijkstra(s,n,g): 
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

def newv(v,s):
  return v*2500+s

s = min(s,2499)
e2 = [[] for _ in range(n*2500)]
for u in range(n):
  for j in range(2500):
    
    
    e2[newv(u,j)].append((newv(u,min(j+c[u],2499)),d[u]))
    for v,a,b in e[u]:
      if j >= a:
        e2[newv(u,j)].append((newv(v,j-a),b))

l = dijkstra(newv(0,s),n*2500,e2)
for i in range(1,n):
  ans = INF
  for j in range(2500):
    ans = min(l[newv(i,j)],ans)
  print(ans)

Solution (Python):


def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            if (n_Ag := ag - fare) < 0: continue
            if time[to][n_Ag] <= (n_time := t + dt): continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        if (e_Ag := ag + exchange[loc][0]) > MX_AG: continue
        if time[loc][e_Ag] <= (e_time := t + exchange[loc][1]): continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    ans = (min(time[to]) for to in range(1, N))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0: continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time: continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG: continue
        cf = time[loc][e_Ag]
        if cf <= e_time: continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    ans = (min(time[to]) for to in range(1, N))

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0: continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time: continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG: continue
        cf = time[loc][e_Ag]
        if cf <= e_time: continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    ans = (min(time[to]) for to in range(1, N))

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from heapq import heappush, heappop

    INF = 1 << 60
    MX_AG = 2500

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add((v, a, b))
        g[v].add((u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append((c, d))

    h = [(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    

    while h:
        t, ag, loc = heappop(h)
        for to, fare, dt in g[loc]:
            n_Ag = ag - fare
            if n_Ag < 0: continue
            cf = time[to][n_Ag]
            n_time = t + dt
            if cf <= n_time: continue
            time[to][n_Ag] = n_time
            heappush(h, (n_time, n_Ag, to))

        e_time = t + exchange[loc][1]
        e_Ag = ag + exchange[loc][0]
        if e_Ag > MX_AG: continue
        cf = time[loc][e_Ag]
        if cf <= e_time: continue
        time[loc][e_Ag] = e_time
        heappush(h, (e_time, e_Ag, loc))

    for to in range(1, N):
        print(min(time[to]))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import dataclasses
    from heapq import heappush, heappop

    @dataclasses.dataclass(frozen=True)
    class Path:
        to: int
        fare: int
        travel_time: int

    @dataclasses.dataclass(frozen=True)
    class ExchangeRate:
        Ag: int
        exchange_time: int

    @dataclasses.dataclass(frozen=True)
    class Traveler:
        consumption_time: int
        remaining_Ag: int
        location: int

        def __gt__(self, other):
            return self.consumption_time > other.consumption_time

        def __eq__(self, other):
            return self.consumption_time == other.consumption_time

    INF = 1 << 60
    MX_AG = 2500

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        g[u].add(Path(v, a, b))
        g[v].add(Path(u, a, b))

    exchange = []
    for _ in range(N):
        c, d = map(int, input().split())
        exchange.append(ExchangeRate(c, d))

    h = [Traveler(0, S, 0)]

    time = [[INF] * (MX_AG + 1) for _ in range(N)]
    time[0][S] = 0
    

    while h:
        t = heappop(h)
        for p in g[t.location]:
            n_Ag = t.remaining_Ag - p.fare
            if n_Ag < 0: continue
            cf = time[p.to][n_Ag]
            n_time = t.consumption_time + p.travel_time
            if cf <= n_time: continue
            time[p.to][n_Ag] = n_time
            heappush(h, Traveler(consumption_time=n_time, remaining_Ag=n_Ag, location=p.to))

        e_time = t.consumption_time + exchange[t.location].exchange_time
        e_Ag = t.remaining_Ag + exchange[t.location].Ag
        if e_Ag > MX_AG: continue
        cf = time[t.location][e_Ag]
        if cf <= e_time: continue
        time[t.location][e_Ag] = e_time
        heappush(h, Traveler(consumption_time=e_time, remaining_Ag=e_Ag, location=t.location))

    for to in range(1, N):
        print(min(time[to]))


if __name__ == '__main__':
    main()

Solution (Python):
def e_two_currencies(INF = float('inf')):
    
    import heapq
    N, M, S = map(int, input().split())

    Edges = [[] for _ in range(N)]
    max_a = 0
    for _ in range(M):
        u, v, a, b = [int(i) for i in input().split()]
        Edges[u - 1].append((v - 1, a, b))
        Edges[v - 1].append((u - 1, a, b))
        max_a = max(max_a, a)

    Exchanges = []
    Times = []
    for n in range(N):
        c, d = [int(i) for i in input().split()]
        Exchanges.append(c)
        Times.append(d)

    max_coin = max_a * N
    initial_silver = min(S, max_coin)  

    
    dist = [[INF] * (max_coin + 1) for _ in range(N)]
    dist[0][initial_silver] = 0
    
    queue = [(0, initial_silver, 0)]

    while queue:
        time, silver, city = heapq.heappop(queue)
        if dist[city][silver] < time:  
            continue

        
        
        
        if (silver + Exchanges[city] < max_coin
                and time + Times[city] < dist[city][silver + Exchanges[city]]):
            dist[city][silver + Exchanges[city]] = time + Times[city]
            heapq.heappush(queue, (time + Times[city], silver + Exchanges[city], city))

        
        for next_city, a, b in Edges[city]:
            
            if silver >= a and time + b < dist[next_city][silver - a]:
                dist[next_city][silver - a] = time + b
                heapq.heappush(queue, (time + b, silver - a, next_city))

    
    ans = [min(d) for d in dist[1:]]
    return ' '.join(map(str, ans))

print(e_two_currencies())

Solution (Python):
import heapq


dp = {}
hq = []

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

MAX_S = (N-1)*50
INF = 10**18
S = min(S, MAX_S)

for i in range(1,N+1):
    dp[i] = {}
    for j in range(MAX_S+1):
        dp[i][j] = INF

uv = {}
for i in range(N):
    uv[i+1] = []
for i in range(M):
    U, V, A, B = map(int, input().split())
    uv[U].append((V,A,B))
    uv[V].append((U,A,B))

c = {}
d = {}
for i in range(N):
    C, D = map(int, input().split())
    c[i+1] = C
    d[i+1] = D

def q_push(v, money, time):
    if money < 0:
        return 
    if dp[v][money] <= time:
        return
    dp[v][money] = time
    heapq.heappush(hq, (time, v, money))


q_push(1,S,0)
while hq:
    now_t, now_v, now_m = heapq.heappop(hq)

    if dp[now_v][now_m] != now_t:
        continue

    new_money = min(now_m+c[now_v],MAX_S)
    q_push(now_v,new_money,now_t+d[now_v])
    for next_v, next_a, next_b in uv[now_v]:
        q_push(next_v,now_m-next_a,now_t+next_b)

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

Solution (Python):
import heapq
def dijkstra_heap():
    used = [-1] * (2451*n)
    edgelist=[]
    heapq.heappush(edgelist,[0,ss])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2451
        used[v] = kai
        for e in edge[v//2451]:
            if mai-e[1]>=0:
                sss=mai-e[1]
                if used[e[2]*2451+sss]==-1:
                    heapq.heappush(edgelist,[e[0]+kai,e[2]*2451+sss])
        if mai+cd[v//2451][0]<=2450:
            if used[v+cd[v//2451][0]]==-1:
                heapq.heappush(edgelist,[kai+cd[v//2451][1],v+cd[v//2451][0]])
    return used


n,m,ss = map(int,input().split())
ss=min(2450,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2451):
        if pp[i*2451+j]!=-1:
            ans=min(ans,pp[i*2451+j])
    print(ans)

Solution (Python):
import heapq
def dijkstra_heap():
    used = [-1] * (2451*n)
    edgelist=[]
    heapq.heappush(edgelist,[0,ss])
    while len(edgelist):
        
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2451
        used[v] = kai
        for e in edge[v//2451]:
            if mai-e[1]>=0:
                sss=mai-e[1]
                if used[e[2]*2451+sss]==-1:
                    heapq.heappush(edgelist,[e[0]+kai,e[2]*2451+sss])
        if mai+cd[v//2451][0]<=2450:
            if used[v+cd[v//2451][0]]==-1:
                heapq.heappush(edgelist,[kai+cd[v//2451][1],v+cd[v//2451][0]])
    return used


n,m,ss = map(int,input().split())
ss=min(2450,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2451):
        if pp[i*2451+j]!=-1:
            ans=min(ans,pp[i*2451+j])
    print(ans)

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: break
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: break
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

Solution (Python):
from heapq import *
N, M, S = map(int, input().split())
graph = [[] for _ in range(N)]
amax = 0
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1
  graph[u].append([v, a, b])
  graph[v].append([u, a, b])
  amax = max(amax, a)
  
lcoins = amax * (N-1)
  
cost = list()
time = list()
for _ in range(N):
  c, d = map(int, input().split())
  cost.append(c)
  time.append(d)

INF = float('INF')
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 + cost[v] < M and dv + time[v] < dist[v][num+cost[v]]:
    dist[v][num+cost[v]] = dv + time[v]
    heappush(q, (dv+time[v], num+cost[v], v))
    
  for next, a, b in graph[v]:
    if num >= a and dv+b < dist[next][num-a]:
      dist[next][num-a] = dv+b
      heappush(q, (dv+b, num-a, next))
      
for i in range(1,N):
  print(min(dist[i]))