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 heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) 

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        if cost[now][ns] <= nt : continue
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) 

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Solution (Python):












from heapq import heappop, heappush


def solve():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]
    
    max_a = 0
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        graph[u - 1].append([v - 1, a, b])
        graph[v - 1].append([u - 1, a, b])
        max_a = max(max_a, a)
    ce = [[int(i) for i in input().split()] for _ in range(n)]
    
    maxSilver = max_a * (n - 1)  
    inf = float('inf')
    ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
    
    q = [[0, 0, min(maxSilver, s)]]  
    ns_map[0][min(maxSilver, s)] = 0  
    while q:
        ti, ni, si = heappop(q)
        
        for g in graph[ni]:
            n2, ai, bi = g
            if si >= ai and ns_map[n2][si - ai] > ti + bi:
                ns_map[n2][si - ai] = ti + bi
                
                
                heappush(q, [ti + bi, n2, si - ai])
        
        ci, di = ce[ni]
        ti += di
        si = min(si + ci, maxSilver)
        if ns_map[ni][si] > ti:
            ns_map[ni][si] = ti
            heappush(q, [ti, ni, si])
    for i in range(1, n):
        print(min(ns_map[i]))


if __name__ == '__main__':
    solve()

Solution (Python):












from heapq import heappop, heappush


def solve():
    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([v - 1, a, b])
        graph[v - 1].append([u - 1, a, b])
    ce = [[int(i) for i in input().split()] for _ in range(n)]
    
    maxSilver = 50 * 49  
    inf = float('inf')
    ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
    
    q = [[0, 0, min(maxSilver, s)]]  
    ns_map[0][min(maxSilver, s)] = 0  
    while q:
        ti, ni, si = heappop(q)
        
        for g in graph[ni]:
            n2, ai, bi = g
            if si >= ai and ns_map[n2][si - ai] > ti + bi:
                ns_map[n2][si - ai] = ti + bi
                
                
                heappush(q, [ti + bi, n2, si - ai])
        
        ci, di = ce[ni]
        ti += di
        si = min(si + ci, maxSilver)
        if ns_map[ni][si] > ti:
            ns_map[ni][si] = ti
            heappush(q, [ti, ni, si])
    for i in range(1, n):
        print(min(ns_map[i]))


if __name__ == '__main__':
    solve()

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


def phi(city, silver):
    return city*2501+silver


def psi(x):
    city = x//2501
    silver = x % 2501
    return city, silver


n, m, s = map(int, input().split())
g = [[] for _ in range(n*2501+1)]

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

for i in range(n):
    c, d = map(int, input().split())
    for j in range(2501):
        if j + c <= 2500:
            g[phi(i, j)].append((phi(i, j+c), d))


def dijkstra(s, n, g):
    
    
    
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


s = min(s, 2500)
d = dijkstra(phi(0, s), n*2501+1, g)

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

Solution (Python):
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from heapq import *

n, m, s = na()
uvab = nan(m)
cd = nan(n)
maxS = 5007
s = min(s, maxS)

g = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = uvab[i]
    u -= 1
    v -= 1
    g[u].append((v, (a, b)))
    g[v].append((u, (a, b)))

def dijkstra(g, x):
    dist = [[inf] * (maxS + 1) for _ in range(len(g))]
    dist[x][s] = 0
    q = []
    
    heappush(q, (0, (x, s)))
    while len(q):
        p = heappop(q)
        a = p[1][0]
        cost = p[0]
        curS = p[1][1]
        
        
        
        for b in g[a]:
            to = b[0]
            ncost = cost + b[1][1]
            nS = curS - b[1][0]
            if nS >= 0:
                if dist[to][nS] > ncost:
                    dist[to][nS] = ncost
                    heappush(q, (ncost, (to, nS)))
        
        c, d = cd[a]
        cost += d
        curS += c
        curS = min(curS, maxS)
        if dist[a][curS] > cost:
            dist[a][curS] = cost
            heappush(q, (cost, (a, curS)))
    
    return dist

dist = dijkstra(g, 0)
for i in range(1, n):
    ans = inf
    for j in range(maxS):
        ans = min(ans, dist[i][j])
    print(ans)

Solution (Python):
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from heapq import *

n, m, s = na()
uvab = nan(m)
cd = nan(n)
maxS = 5007
s = min(s, maxS)

g = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = uvab[i]
    u -= 1
    v -= 1
    g[u].append((v, (a, b)))
    g[v].append((u, (a, b)))

def dijkstra(g, x):
    dist = [[inf] * (maxS + 1) for _ in range(len(g))]
    dist[x][s] = 0
    q = []
    
    heappush(q, (0, (x, s)))
    while len(q):
        p = heappop(q)
        a = p[1][0]
        cost = p[0]
        curS = p[1][1]
        
        
        
        for b in g[a]:
            to = b[0]
            ncost = cost + b[1][1]
            nS = curS - b[1][0]
            if nS >= 0:
                if dist[to][nS] > ncost:
                    dist[to][nS] = ncost
                    heappush(q, (ncost, (to, nS)))
        
        c, d = cd[a]
        cost += d
        curS += c
        curS = min(curS, maxS)
        if dist[a][curS] > cost:
            dist[a][curS] = cost
            heappush(q, (cost, (a, curS)))
    
    return dist

dist = dijkstra(g, 0)
for i in range(1, n):
    ans = inf
    for j in range(maxS):
        ans = min(ans, dist[i][j])
    print(ans)

Solution (Python):
N, M, S = map(int,input().split())
ubab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

from heapq import heappush, heappop

routes = [[] for _ in range(N)]
max_money = 0
for u, v, a, b in ubab:
    routes[u-1].append([b, -a, v-1]) 
    routes[v-1].append([b, -a, u-1])
    if a > max_money:
        max_money = a

for i, (c, d) in enumerate(cd):
    routes[i].append([d,+c,i])

max_pocessing = max_money * (N-1)

minimum = [[10e+1000 for _ in range(max_pocessing+1)] for _ in range(N)] 
if S>max_pocessing:
    S = max_pocessing
minimum[0][S] = 0
last_num = 0
last_money = S 
hp = []


while True:
    for cost, money, num in routes[last_num]:
        if last_money+money >= max_pocessing:
            money = max_pocessing - last_money
        if minimum[num][last_money+money] == 10e+1000:
            heappush(hp, (minimum[last_num][last_money]+cost, last_money+money, num))    
    while len(hp)>0:
        candidate_cost, candidate_money, candidate_num = heappop(hp)
        if minimum[candidate_num][candidate_money] == 10e+1000 and candidate_money >= 0:
            break
    else:
        break
    last_num = candidate_num
    last_money = candidate_money
    minimum[candidate_num][candidate_money] = candidate_cost

for each_minimum in minimum[1:]:
    print(min(each_minimum))

Solution (Python):
import sys
input=sys.stdin.buffer.readline
from heapq import heappop,heappush,heapify
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((v-1,a,b))
  graph[v-1].append((u-1,a,b))
cd=[tuple(map(int,input().split())) for _ in range(N)]
INF=1e18
S=min(S,2500)
time=[[INF]*2501 for _ in range(N)]
q=[(0,0,S)]
heapify(q)
while q:
  now_time,cur_city,cur_coin=heappop(q)
  for nxt_city,cost,dt in graph[cur_city]:
    if cur_coin>=cost and time[nxt_city][cur_coin-cost]>now_time+dt:
      time[nxt_city][cur_coin-cost]=now_time+dt
      heappush(q,(now_time+dt,nxt_city,cur_coin-cost))
  c,d=cd[cur_city]
  new_coin=min(2500,cur_coin+c)
  nxt_time=now_time+d
  if nxt_time<time[cur_city][new_coin]:
    time[cur_city][new_coin]=nxt_time
    heappush(q,(nxt_time,cur_city,new_coin))
for i in range(1,N):
  print(min(time[i]))

Solution (Python):
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

"""
無向グラフでdpできるのが非直感的だが（というのも普通dpをするのはDAGに限るから）、
まず無向グラフは各辺に対して向きの違う有向辺が２本走っていると思えば一応有向グラフではある。

ダイクストラ自体はacyclicityは要請しないので実行可能だが、このとき各頂点への最短距離を小さい順に並べる。
    （例） S--->A--->B--->C--->D--->E
すると実は元のグラフからA--->SやC--->Bといった上の順番と逆行するような辺を除いてもダイクストラの結果は同じになる。
（というのも負辺は無いので逆向きの辺を使うと経路長が長くなるから）

そもそもダイクストラで最小値を取って更新をかけているのはまさに上のような間引いたグラフを構築しているわけで、これは
まさにDAGになっている。なのでこの上でdpを走らせることも可能。

そしてダイクストラとdpを同時に実行できる点が奇跡なのであって、本問のような一般グラフ上でのDAG生成＆dpを俗に
「拡張ダイクストラ」とも言うらしい。
"""

def main():
    N, M, S = map(int, input().split())
    MAX_S = 50 * N + 1
    repn = [[] for _ in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        repn[u - 1].append((v - 1, a, b))
        repn[v - 1].append((u - 1, a, b))
    coin = []
    for _ in range(N):
        c, d = map(int, input().split())
        coin.append((c, d))

    """
    「最短路問題はダイクストラだが、実質それはdpと見れるらしい。」
    重要になるパラメーターは
        ・頂点　・お金　・時間
    なのでdp[v][s][x]が最初に思いつくが確実にTLE、
    ただし移動にかかるお金は制約が強いので
        dp[v][s] = (頂点vに手持ちs円でたどり着く最小の時間)
    とすればよい。
    このときお金sの状態数は上限50*(N-1)とすれば十分。
    (これだけあれば一切換金が不要なので)

    dpの遷移は「辺を移動」、「換金する」の２つあることに注意。
    この遷移を式にする際にダイクストラを用いる。
    """

    dp = [[float("inf")] * (MAX_S + 1) for _ in range(N)]
    S = min(S, MAX_S)
    q = []

    
    def push(x, v, s):
        if not (s < 0 or dp[v][s] <= x):
            dp[v][s] = x
            heappush(q, (x, v, s))
    
    
    push(0, 0, S)

    
    while q:
        x, v, s = heappop(q)
        if (dp[v][s] != x): continue 
        
        new_x = x + coin[v][1]
        new_s = min(s + coin[v][0], MAX_S)
        push(new_x, v, new_s)
        
        for u, a, b in repn[v]:
            push(x + b, u, s - a)
    
    
    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S):
            ans = min(ans, dp[v][s])
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N, M, S = map(int, input().split(" "))
adj = [ [] for _ in range(N) ] 
convert = []
for _ in range(M) :
    u, v, a, b = map(int, input().split(" "))
    adj[u-1].append( (v-1,a,b) )
    adj[v-1].append( (u-1,a,b) )

for _ in range(N) :
    c, d = map(int, input().split(" "))
    convert.append( (c, d) )  

import heapq 

limit = 2500
S = min(S, limit)
h = [ (0, 0, S) ] 
ans = [  [float('inf')]*(limit+1) for _ in range(N) ]

while h != [] :
    time_consumed, city, coin = heapq.heappop(h)
    if ans[city][coin] < time_consumed:
        continue
    ans[city][coin] = time_consumed
    
    if coin + convert[city][0] < limit and ans[city][coin + convert[city][0]] > time_consumed + convert[city][1] :
        ans[city][coin + convert[city][0]] = time_consumed + convert[city][1]
        heapq.heappush(h, (time_consumed + convert[city][1], city, coin+convert[city][0] ) )

    for v, a, b in adj[city] :
        if coin - a < 0 or ans[v][coin-a] <= time_consumed+b :
            continue
        ans[v][coin-a] = time_consumed+b
        heapq.heappush( h, (time_consumed+b, v, coin-a) )
    
for i in range(1, N) :
    print(min(ans[i]))

Solution (Python):
import sys
input=sys.stdin.buffer.readline
from heapq import heappop,heappush
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((v-1,a,b))
  graph[v-1].append((u-1,a,b))
cd=[tuple(map(int,input().split())) for _ in range(N)]
INF=1e18
S=min(S,2500)
time=[[INF]*2501 for _ in range(N)]
q=[(0,0,S)]
while q:
  now_time,cur_city,cur_coin=heappop(q)
  for nxt_city,cost,dt in graph[cur_city]:
    if cur_coin>=cost and time[nxt_city][cur_coin-cost]>now_time+dt:
      time[nxt_city][cur_coin-cost]=now_time+dt
      heappush(q,(now_time+dt,nxt_city,cur_coin-cost))
  c,d=cd[cur_city]
  new_coin=min(2500,cur_coin+c)
  nxt_time=now_time+d
  if nxt_time<time[cur_city][new_coin]:
    time[cur_city][new_coin]=nxt_time
    heappush(q,(nxt_time,cur_city,new_coin))
for i in range(1,N):
  print(min(time[i]))

Solution (Python):
from heapq import heappop,heappush
import sys
input=sys.stdin.buffer.readline
N,M,S=map(int,input().split())
INF=10**18
Time=[[INF]*2501 for _ in range(N)]
graph=[[] for _ in range(N)]
S=min(S,2500)
for _ in range(M):
    u,v,a,b=map(int,input().split())
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

cd=[tuple(map(int,input().split())) for _ in range(N)]

hq=[(0,0,S)] 
while hq:
    ct,cur_city,si=heappop(hq)
    for nxt_city,cost,t in graph[cur_city]:
        if si>=cost:
            new_t=ct+t
            if new_t<Time[nxt_city][si-cost]:
              Time[nxt_city][si-cost]=new_t
              heappush(hq,(new_t,nxt_city,si-cost))
    c,d=cd[cur_city]
    v_new=min(si+c,2500)
    t_new=ct+d
    if t_new<Time[cur_city][v_new]:
      Time[cur_city][v_new]=t_new
      heappush(hq,(t_new,cur_city,v_new))
for i in range(1,N):
    print(min(Time[i]))

Solution (Python):
max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)

Solution (Python):
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

S=min(S,2450)
di=[inf]*2451*N
di[S]=0
hq=[(0,S)] 

while hq:
    t,v=heappop(hq)
    u=v//2451 
    s=v%2451 
    if t>di[v]:
        continue

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    c=min(c,2450-s)
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=min(di[i*2451:(i+1)*2451])
    print(m)

Solution (Python):
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = 10**18
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] 

while hq:
    t,v=heappop(hq)
    u=v//2451 
    s=v%2451 

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

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

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

    dp = [[float('inf')] * 2510 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 edge[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+exchange[v][0], 2500)
        if dp[v][nm] > dp[v][money] + exchange[v][1]:
            dp[v][nm] = dp[v][money] + exchange[v][1]
            heappush(q, (dp[v][nm], v, nm))

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


if __name__ == "__main__":
    main()

Solution (Python):
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] 

while hq:
    t,v=heappop(hq)
    u=v//2451 
    s=v%2451 

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

Solution (Python):
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] 

while hq:
    t,v=heappop(hq)
    if t>di[v]:
        continue
    u=v//2451 
    s=v%2451 

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

Solution (Python):
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


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

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] 

while hq:
    t,v=heappop(hq)
    u=v//2451 
    s=v%2451 

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

Solution (Python):
INF=10**30
from heapq import heappush,heappop,heapify
def dijkstra(G,coin,s,n):
    que=[(0,[coin,s])]
    dist=[[INF]*n for i in range(2501)]
    dist[coin][s]=0
    while que:
        mincost,co=heappop(que)
        nowc,nowv=co[0],co[1]
        if(mincost>dist[nowc][nowv]):
            continue
        for v,c,x in G[nowc][nowv]:
            if(dist[nowc][nowv]+c<dist[x][v]):
                dist[x][v]=dist[nowc][nowv]+c
                heappush(que,(dist[x][v],[x,v]))
    return dist

N,M,S=map(int,input().split())
if(S>=2500):
    S=2500
G=[[[] for i in range(N)] for i in range(2501)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    for i in range(2501):
        if i-a>=0:
            G[i][u].append([v,b,i-a])
            G[i][v].append([u,b,i-a])
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2500):
        if j+c<=2500:
            G[j][i].append([i,d,j+c])

dist=dijkstra(G,S,0,N)

for i in range(1,N):
    res=10**30
    for j in range(2501):
        res=min(res,dist[j][i])
    print(res)

Solution (Python):


import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) 
    adj[v].append((u, a, b)) 
    max_silver += a 
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) 

s = min(s, max_silver) 





dist = {(1, s): 0}  
queue = [(0, 1, s)]
dmin = {1: 0} 
nfin = 1      

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  
            break
    
    for v, a, b in adj[u]:
        if si < a:  
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])