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

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, m, s = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
    u, v, a, b = nm()
    u -= 1; v -= 1
    for j in range(0, N, n):
        if v + j - a * n >= 0:
            G[u + j].append((v + j - a * n, b))
        if u + j - a * n >= 0:
            G[v + j].append((u + j - a * n, b))
for u in range(n):
    c, d = nm()
    for j in range(0, N, n):
        G[u + j].append((min(u + j + c * n, u + N - n), d))

import heapq as hq

def dijkstra(G, s, t=None):
    """
    G[v] = [(x1, c1), (x2, c2), ...]
    """
    dist = [-1]*len(G)
    dist[s] = 0
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] < 0 or dist[x] > d + c:
                dist[x] = d + c
                hq.heappush(q, (d + c, x))
    if t is None:
        return dist
    else:
        return dist[t]

dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
    print(min(dist[i::n]))

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import queue
    mod=10**9+7
    N,M,S=MI()
    
    
    NN=N*50+1
    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        """
        
        
        
        
        class Edge():
            
            
            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost
        
        def __init__(self, V):
            
            self.G = [[] for _ in range(V)] 
            self. _E = 0 
            self._V = V 
        
        
        def E(self):
            return self._E
        
        
        def V(self):
            return self._V
        
        def add(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1
            
        def add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2
            
        def shortest_path(self,s):
            
            
            que = [] 
            d = [float("inf")] * self.V()
            prev = [None]*self.V() 
            d[s] = 0
            heapq.heappush(que,(0,s)) 
            
            while len(que)!=0:
                
                cost,v = heapq.heappop(que)
                
                
                if d[v] < cost:
                    continue
                    
                
                for i in range(len(self.G[v])):
                    e = self.G[v][i] 
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost 
                        prev[e.to] = v
                        heapq.heappush(que,(d[e.to],e.to)) 
            
            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            
                        
            return d
    
    djk=Dijkstra(N*NN)
    
    for i in range(M):
        u,v,a,b=MI()
        u-=1
        v-=1
        for j in range(a,NN):
            djk.add(u*NN+j,v*NN+j-a,b)
            djk.add(v*NN+j,u*NN+j-a,b)
    for i in range(N):
        c,d=MI()
        for j in range(0,NN-c,1):
            djk.add(i*NN+j,i*NN+j+c,d)
            
    dL=djk.shortest_path(min(S,NN-1))
    for i in range(1,N):
        ans=10**20
        for j in range(0,NN):
            ans=min(ans,dL[i*NN+j])
        print(ans)
        
        
    

main()

Solution (Python):
import heapq
import sys

def main():

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

    edges = [[[] for _ in range(n)] for _ in range(2501)]

    for u,v,a,b in uvab:
        for i in range(a,2501):
            edges[i][u-1].append(((v-1, i-a), b))
            edges[i][v-1].append(((u-1, i-a), b))

    for i in range(n):
        c,d = cd[i]
        for j in range(2501):
            edges[j][i].append(((i, min(j+c, 2500)), d))

    def dijkstra(edges, c):
        hq = []
        d = [[10**20] * n for _ in range(c)]
        d[min(2500, s)][0] = 0
        heapq.heappush(hq, (0, (0, min(2500, s))))
        while hq:
            d1, p = heapq.heappop(hq)
            for p2, d2 in edges[p[1]][p[0]]:
                if d[p2[1]][p2[0]] == -1 or d[p2[1]][p2[0]] > d1 + d2:
                    d[p2[1]][p2[0]] = d1 + d2
                    heapq.heappush(hq, (d1+d2, p2))
        return d

    dis = dijkstra(edges, 2501)
    ans = [10**20]*n
    for i in range(2501):
        for j in range(n):
            ans[j] = min(ans[j], dis[i][j])

    for i in ans[1:]:
        print(i)

if __name__ == '__main__':
    main()

Solution (Python):
import sys;input=sys.stdin.readline
from heapq import *
def dijkstra(s,cost):
    d = [float("inf")] * NN
    used = [False] * NN
    d[s] = 0
    while True:
        v = -1
        for i in range(NN):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            return d
        used[v] = True
        for j, c in cost[v]:
            d[j] = min(d[j],d[v]+c)

def dijkstra_heapq(s, cost):
    d = [float("inf")] * NN
    h = [(0, s)]
    d[s] = 0
    while h:
        vc, v = heappop(h)

        if vc > d[v]:
            continue
        for j, c in cost[v]:
            if vc+c<d[j]:
                d[j] = vc+c
                heappush(h, (vc+c, j))
    return d

N,W,S = map(int,input().split())
V = 2500
NN = N*(V+1)

def enc(u, v):
    return u*NN + v


cost = [[] for _ in range(NN)]
for i in range(W):
    x,y,z,u = map(int,input().split())
    x -= 1
    y -= 1
    for v in range(V+1):
        if v-z>=0:
            cost[x*(V+1)+v].append((y*(V+1)+v-z, u))
            cost[y*(V+1)+v].append((x*(V+1)+v-z, u))

for i in range(N):
    x, y = map(int, input().split())
    for v in range(V+1):
        cost[i*(V+1)+v].append((i*(V+1)+min(v+x, V), y))

S = min(V, S)
d = dijkstra_heapq(S,cost)
for i in range(1, N):
    print(min(d[i*(V+1):(i+1)*(V+1)]))

Solution (Python):
import sys


import heapq
class Dijkstra:
    INF = 10**18

    def __init__(self, N, Graph=[[-1]]):
        self.N = (N+1)
        self.dist = [self.INF] * (N+1)
        if Graph[0][0]!=-1: self.G = Graph
        else: self.G = [[] for _ in range(N+1)]

    def insert(self, From, To, Cost):
        self.G[From].append([To, Cost])

    def reset(self):
        for i in range(self.N): self.dist[i] = self.INF

    def dijkstra(self, st):
        self.reset()
        hq = [(0, st)]
        heapq.heapify(hq)
        while len(hq):
            tmp = heapq.heappop(hq)
            now, now_dist = tmp[1], tmp[0]
            if self.dist[now] <= now_dist: continue
            self.dist[now] = now_dist
            for to in self.G[now]:
                heapq.heappush(hq, (now_dist+to[1], to[0]))

def main():
    input=sys.stdin.readline
    n, m, s = map(int, input().split())
    MAX_MONEY = 2600
    dj = Dijkstra((n+1)*(MAX_MONEY+1))

    for i in range(m):
        a, b, c, d = map(int, input().split())
        a, b = a-1, b-1
        for j in range(c, MAX_MONEY):
            dj.insert(a*MAX_MONEY+j, b*MAX_MONEY+(j-c), d)
            dj.insert(b*MAX_MONEY+j, a*MAX_MONEY+(j-c), d)

    for i in range(n):
        a, b = map(int, input().split())
        for j in range(MAX_MONEY-a-1):
            dj.insert(i*MAX_MONEY+j, i*MAX_MONEY+(j+a), b)

    s = min(s, MAX_MONEY-1)
    dj.dijkstra(0*MAX_MONEY+s)

    for i in range(1, n):
        ans = 10**18
        for j in range(MAX_MONEY):ans = min(ans, dj.dist[i*MAX_MONEY + j])
        print(ans)

if __name__=="__main__":
  main()

Solution (Python):
import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max)
    dp = [[float("inf")]*(money_max+1) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = 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())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0, S])
    while 0 < len(q):
        pre_time, idx, s = heapq.heappop(q)
        if dp[idx][s] < pre_time:
            continue
        ex = min(s + exchange[idx][0], money_max)
        if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
            dp[idx][ex] = dp[idx][s] + exchange[idx][1]
            heapq.heappush(q, [dp[idx][ex], idx, ex])
        for to, money, time in G[idx]:
            if money <= s:
                if dp[idx][s] + time < dp[to][s-money]:
                    dp[to][s-money] = dp[idx][s] + time
                    heapq.heappush(q, [dp[to][s-money], to, s-money])
    for i in range(1, N):
        print(min(dp[i]))

if __name__ == "__main__":
    main()

Solution (Python):


from heapq import heappop, heappush


INF = 10 ** 18


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


def solve(link):
    ans = {}
    lim = 50 * (N - 1)
    w = [[INF] * (lim + 1) for _ in range(N)]

    
    hq = [(0, 0, min(S, lim))]
    while hq:
        t, v, s = heappop(hq)
        if t > w[v][s]:
            continue
        if v not in ans:
            ans[v] = t
            if len(ans) == N:
                break
        
        
        if s < lim:
            c, d = CD[v]
            new_s = min(lim, s + c)
            new_t = t + d
            if new_t < w[v][new_s]:
                w[v][new_s] = new_t
                heappush(hq, (new_t, v, new_s))
        
        
        for u, a, b in link[v]:
            if s < a:
                continue
            new_s = s - a
            new_t = t + b
            if new_t < w[u][new_s]:
                w[u][new_s] = new_t
                heappush(hq, (new_t, u, new_s))
        
    return ans


def main():
    link = [[] for _ in range(N)]
    for u, v, a, b in UVAB:
        link[u - 1].append((v - 1, a, b))
        link[v - 1].append((u - 1, a, b))
    
    ans = solve(link)
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

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

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

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

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

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

N, M, S, *I = map(int, open(0).read().split())
UVAB, CD = I[:4 * M], I[4 * M:]

R, C, V = [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    for i in range(2501 - a):
        R += [(i + a) * 51 + u, (i + a) * 51 + v]
        C += [i * 51 + v, i * 51 + u]
        V += [b, b]

for i, (c, d) in enumerate(zip(*[iter(CD)] * 2), 1):
    for j in range(2501 - c):
        R.append(j * 51 + i)
        C.append((j + c) * 51 + i)
        V.append(d)

D = dijkstra(
    csr_matrix((V, (R, C)), [2500 * 60] * 2),
    indices=min(2500, S) * 51 + 1
)

for i in range(2, N + 1):
    print(int(D[i::51].min()))

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

DEBUG = False
INF = float('inf')
MAX_N = 50
MAX_A = 50

N, M, S = map(int, input().split())
U = []
V = []
A = []
B = []
C = []
D = []

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

if DEBUG:
    print("U: {}".format(U))
    print("V: {}".format(V))
    print("A: {}".format(A))
    print("B: {}".format(B))
    print("C: {}".format(C))
    print("D: {}".format(D))
    print("connect: {}".format(connect))

MAX_N = N
MAX_A = max(A)
MAX_MONEY = MAX_N * MAX_A
S = min(S, MAX_MONEY-1)

node = [INF for _ in range(MAX_MONEY * N)]
hq = []
heappush(hq, (0, S))
while hq:
    time, current_node = heappop(hq)
    if DEBUG:
        print("time: {}, current_node: {}, len(hq): {}".format(time, current_node, len(hq)))
    if time < node[current_node]:
        node[current_node] = time
    else:
        continue
    index_city = current_node // MAX_MONEY
    money = current_node % MAX_MONEY
    if DEBUG:
        print("money: {}".format(money))

    for index_next_city, a, b in connect[index_city]:
        if money >= a and time+b < node[index_next_city*MAX_MONEY + money-a]:
            heappush(hq, (time+b, index_next_city*MAX_MONEY + money-a))
    if money < MAX_MONEY-1:
        heappush(hq, (time+D[index_city], min(money+C[index_city], MAX_MONEY-1)+MAX_MONEY*index_city))

for i in range(1,N):
    if DEBUG:
        print("node{}: {}".format(i, node[MAX_MONEY*i:MAX_MONEY*(i+1)]))
    print(min(node[MAX_MONEY*i:MAX_MONEY*(i+1)]))

Solution (Python):
import heapq

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

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

ans = [-1] * N
d = dict()
d[(S, 0)] = 0  
Q = [(0, S, 0)]  
sum_reached = 0
reached = [False] * N

while Q:
    t, sv, st = heapq.heappop(Q)
    if not reached[st]:
        ans[st] = t
        reached[st] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_key = (min(max_silver, sv + cd[st][0]), st)
    new_value = t + cd[st][1]
    if new_key not in d or d[new_key] > new_value:
        d[new_key] = t + cd[st][1]
        heapq.heappush(Q, (new_value, *new_key))

    for dist, a, b in railways[st]:
        if sv >= a:
            new_key = (sv - a, dist)
            new_value = t + b
            if new_key not in d or d[new_key] > new_value:
                d[new_key] = new_value
                heapq.heappush(Q, (new_value, *new_key))

print(*ans[1:], sep="\n")

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
INF = float('inf')

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

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

def Extdijkstra(start):
    global S
    N_d = len(graph)
    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 graph[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(0)
for i in range(1, N):
	print(min(d[i]))

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

def dijkstra(Route,v,start):
    Dist=[float('inf')]*v
    Dist[start]=0
    Visited=[False]*v
    hq=[(0,start)]
    while hq:
        dist,fr=heapq.heappop(hq)
        Visited[fr]=True
        for to,cost in Route[fr]:
            if (not Visited[to]) and Dist[to]>dist+cost:
                Dist[to]=dist+cost
                heapq.heappush(hq,(Dist[to],to))
    return Dist

def main():
    n,m,s=map(int,input().split())
    s_max=2500
    Edges=[[] for _ in range(n*s_max)]
    for _ in range(m):
        u,v,cost,time=map(int,input().split())
        u-=1; v-=1
        for i in range(cost,s_max):
            Edges[u*s_max+i].append((v*s_max+i-cost,time))
            Edges[v*s_max+i].append((u*s_max+i-cost,time))
    Change=[None]*n
    for i in range(n):
        change,time=map(int,input().split())
        for j in range(s_max-change):
            Edges[i*s_max+j].append((i*s_max+j+change,time))
    Dist=dijkstra(Edges,n*s_max,min(s,s_max-1))
    for i in range(1,n):
        print(min(Dist[i*s_max:(i+1)*s_max]))
    
if __name__=='__main__':
    main()

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Solution (Python):

from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, n * 50)

edges = [[] for _ in range(n + 1)]


for _ in range(m):  
    u, v, a, b = map(int, input().split())
    edges[v].append((u, a, b))
    edges[u].append((v, a, b))

exchange = [(0, 0)] * (n + 1)

for edge_num in range(1, n + 1):  
    c, d = map(int, input().split())
    exchange[edge_num] = (c, d)

start = 1

dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]


def dijkstra(edges, start, s, dp):
    dp[start][s] = 0
    edgelist = []
    heappush(edgelist, (0, s, start))  
    while edgelist:
        nowtime, nowmoney, nowedge = heappop(edgelist)
        
        if dp[nowedge][nowmoney] != nowtime:
            continue
        
        deltamoney, deltatime = exchange[nowedge]
        nextmoney = min(nowmoney + deltamoney, n * 50)
        nexttime = nowtime + deltatime
        if dp[nowedge][nextmoney] > nexttime:
            dp[nowedge][nextmoney] = nexttime
            heappush(edgelist, (nexttime, nextmoney, nowedge))
        
        for v, vmoney, vtime in edges[nowedge]:
            nexttime = nowtime + vtime
            nextmoney = nowmoney - vmoney
            if nextmoney < 0:
                continue
            if dp[v][nextmoney] > nexttime:
                dp[v][nextmoney] = nexttime
                heappush(edgelist, (nexttime, nextmoney, v))
    return dp


time = dijkstra(edges, start, s, dp)

ans = [infi] * (n + 1)
for i in range(1, n + 1):
    for j in range(n * 50 + 1):
        ans[i] = min(ans[i], dp[i][j])

print(*ans[2 : (n + 1)], sep="\n")

Solution (Python):

from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, n * 50)

edges = [[] for _ in range(n + 1)]


for _ in range(m):  
    u, v, a, b = map(int, input().split())
    edges[v].append((u, a, b))
    edges[u].append((v, a, b))

exchange = [(0, 0)] * (n + 1)

for edge_num in range(1, n + 1):  
    c, d = map(int, input().split())
    exchange[edge_num] = (c, d)

start = 1

dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]


def dijkstra(edges, start, s, dp):
    dp[start][s] = 0
    edgelist = []
    heappush(edgelist, (0, s, start))  
    while edgelist:
        nowtime, nowmoney, nowedge = heappop(edgelist)
        
        if dp[nowedge][nowmoney] != nowtime:
            continue
        
        deltamoney, deltatime = exchange[nowedge]
        nextmoney = min(nowmoney + deltamoney, n * 50)
        nexttime = nowtime + deltatime
        if dp[nowedge][nextmoney] > nexttime:
            dp[nowedge][nextmoney] = nexttime
            heappush(edgelist, (nexttime, nextmoney, nowedge))
        
        for v, vmoney, vtime in edges[nowedge]:
            nexttime = nowtime + vtime
            nextmoney = nowmoney - vmoney
            if nextmoney < 0:
                continue
            if dp[v][nextmoney] > nexttime:
                dp[v][nextmoney] = nexttime
                heappush(edgelist, (nexttime, nextmoney, v))
    return dp


time = dijkstra(edges, start, s, dp)

ans = [infi] * (n + 1)
for i in range(1, n + 1):
    for j in range(n * 50 + 1):
        ans[i] = min(ans[i], dp[i][j])

print(*ans[2 : (n + 1)], sep="\n")

Solution (Python):
from heapq import *

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

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = map(int, input().split())
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    
    
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

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

Solution (Python):
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,S = Ints()
from collections import defaultdict
Graph  = defaultdict(list)

for i in range(M):
    u,v,a,b = Ints()
    Graph[u-1].append([v-1,a,b])
    Graph[v-1].append([u-1,a,b])

City = [0]*N
for i in range(N):
    c,d = Ints()
    City[i] = [c,d]

import heapq
que = []

heapq.heappush(que, [0, 0, min(S,5000)])
ans = [[10**16]*5001 for i in range(N)]


while que != []:
    time, nowhere, money = heapq.heappop(que)
    
    if time <= ans[nowhere][money]:
        ans[nowhere][money] = time
        c,d = City[nowhere]
        if time+d < ans[nowhere][min(5000,money+c)]:
            ans[nowhere][min(5000,money+c)] = time+d
            
            heapq.heappush(que, [time+d, nowhere, min(5000,money+c)])
        for (to,a,b) in Graph[nowhere]:
            if 0 <= money - a and time+b < ans[to][min(5000,money-a)]:
                ans[to][min(5000,money-a)] = time+b
                
                heapq.heappush(que, [time+b, to, min(5000,money-a)])

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

Solution (Python):
from heapq import *

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

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

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