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 heapq

N,M,S = list(map(int, input().rstrip().split()))
UVAB_list = [list(map(int, input().rstrip().split())) for i in range(M)]
CD_list = [list(map(int, input().rstrip().split())) for i in range(N)]


max_money = 2500
S = min(max_money, S)


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


change = [None] + [ () for _ in range(N) ]


dp = [None] + [ [float("inf")]*(max_money + 1) for _ in range(N) ]
dp[1][S] = 0


for u,v,a,b in UVAB_list:
    graph[u].append( (v,a,b) )
    graph[v].append( (u,a,b) )

for i,(c,d) in enumerate(CD_list):
    change[i+1] = (c,d)


heap = [ (0, 1, S) ]


while heap:
    cur_time, cur_city, cur_mone = heapq.heappop(heap)
    
    
    changed_money = cur_mone + change[cur_city][0]
    changed_time = cur_time + change[cur_city][1]
    
    if (changed_money <= max_money) and (changed_time < dp[cur_city][changed_money] ):
        dp[cur_city][changed_money] = changed_time
        heapq.heappush(heap, ( changed_time, cur_city, changed_money) )
    
    
    for next_city, cost_coin, cost_time in graph[cur_city]:
        next_time = cur_time + cost_time
        next_money = min( max_money , cur_mone - cost_coin )
        
        if (cur_mone >= cost_coin) and ( next_time < dp[next_city][next_money] ):
            dp[next_city][next_money] = next_time
            heapq.heappush(heap, ( next_time, next_city, next_money) )


for row in dp[2:]:
    print( min(row) )

Solution (Python):
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    
    ans = 0
    C = Counter(D)
    
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    def dijkstra(n, edges, start, C, silver):
        maxC = (2*n-1)*50
        dist = [[inf]*(maxC+1) for _ in range(n)]
        dist[start][silver] = 0
        Q = [(0, (start, silver))]  
        while (Q):
            d, (v, c) = heapq.heappop(Q)
            if dist[v][c]<d:continue
            loop = (maxC-c)//C[v][0] + 1
            for i in range(loop):
                nextc = c+i*C[v][0]
                nextd = d+i*C[v][1]
                if nextc>maxC:
                    nextc=maxC
                if dist[v][nextc] < nextd: continue  
                for u, cost, coin in edges[v]:
                    k = nextc-coin
                    if k<0:
                        continue
                    if dist[u][k] > nextd + cost:
                        dist[u][k] = nextd + cost
                        heapq.heappush(Q, (dist[u][nextc-coin], (u, k)))
        return dist
    N, M, S = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t, a, b = LI()
        s -= 1; t -= 1
        V[s].append((t,b,a))
        V[t].append((s,b,a))
    C = [LI()for _ in range(N)]
    D = dijkstra(N,V,0,C,min(S,(2*N-1)*50))
    for i in range(1,N):
        print(min(D[i]))
    return

def examE2():
    def dijkstra(edges, start=0):
        dist = [inf] * len(edges)
        dist[start] = 0
        Q = [(0, start)]  
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  
            for u, cost in edges[v]:
                if dist[u] > dist[v] + cost:
                    dist[u] = dist[v] + cost
                    heapq.heappush(Q, (dist[u], u))
        return dist
    maxS = 2501
    N, M, S = LI()
    V = [[]for _ in range(N*(maxS+1))]

    for _ in range(M):
        u, v, a, b = LI()
        u -= 1; v -= 1
        for i in range(a, maxS):
            V[u * maxS + i].append([v * maxS + i - a, b])
            V[v * maxS + i].append([u * maxS + i - a, b])
    for i in range(N):
        c, d = LI()
        for j in range(maxS-1):
            V[i * maxS + j].append([i * maxS + min(j + c, maxS-1), d])
    
    D = dijkstra(V,min(maxS-1,S))
    
    

    for i in range(1,N):
        print(min(D[i*maxS:(i+1)*maxS]))
    return

def examF():
    N = I()
    S = LI()
    T = LI()
    U = LI()
    V = LI()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

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


tmp = [list(map(int, input().split())) for _ in range(M)]

U = [0 for _ in range(M)]
V = [0 for _ in range(M)]
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]

for i in range(M):
  U[i] = tmp[i][0] -1
  V[i] = tmp[i][1] -1
  A[i] = tmp[i][2]
  B[i] = tmp[i][3]
A_m = max(A)
S = min(N*A_m, S)


I = [[] for _ in range(N * (N*A_m+1))] 

for i in range(M):
  for j in range(A[i], N*A_m+1):
    I[U[i]*(N*A_m+1)+j].append((V[i]*(N*A_m+1)+j-A[i],B[i]))
    I[V[i]*(N*A_m+1)+j].append((U[i]*(N*A_m+1)+j-A[i],B[i]))

for i in range(N):
  C, D = map(int, input().split())
  for j in range(N*A_m+1):
    I[i*(N*A_m+1)+j].append((i*(N*A_m+1)+min(C+j,N*A_m),D))


def dijkstra(I):
  N = len(I)
  task = [] 
  visited = [0 for _ in range(N)]
  min_cost = [0 for _ in range(N)]
  cost = [10**20 for _ in range(N)]
  prev_points = [0 for _ in range(N)]
  heappush(task, (0, S, -1))
  
  
  
  flag = 0
  while task:
    while task:
      c, p, prev = heappop(task)    
      if visited[p] == 0:
        break  
      if len(task) == 0:
        flag = 1
    if flag == 1:
      break
    
    visited[p] = 1
    min_cost[p] = c
    prev_points[p] = prev
  
    for j, c_ad in I[p]: 
      if visited[j] == 1: continue
      
      cost_next = next_cost(I, p, j, c, c_ad)
      if cost[j] > cost_next:
        cost[j] = cost_next
        heappush(task, (cost_next, j, p))

  return (min_cost, prev_points)

def next_cost(I, p, j, c, c_ad): 

  return c + c_ad

min_cost, prev_points = dijkstra(I)

for i in range(1, N):
  print(min(min_cost[i*(N*A_m+1):(i+1)*(N*A_m+1)]))

Solution (Python):
n,m,s = map(int,input().split())
import collections
g = [[] for _ in range(n+1)]
dic = {}
for _ in range(m):
    u,v,a,b = map(int,input().split())
    g[u].append(v)
    g[v].append(u)
    dic[(u,v)]=(a,b)
    dic[(v,u)]=(a,b)
arr = [[0,0]]+[list(map(int,input().split())) for _ in range(n)]
cost =[[float('inf')]*2501 for _ in range(n+1)]
for i in range(min(2500,s)+1):
    cost[1][i] = 0
q=collections.deque()
q.append(1)
while q:
    v = q.popleft()
    c,d = arr[v]
    for i in range(c,2501):
        cost[v][i] = min(cost[v][i],cost[v][i-c]+d)
    for u in g[v]:
        a,b = dic[(v,u)]
        flag = False
        for i in range(a,2501):
            if cost[u][i-a]>cost[v][i]+b:
                cost[u][i-a]=cost[v][i]+b
                flag = True
        if flag==True:
            q.append(u)
for i in range(2,n+1):
    print(min(cost[i]))

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    from collections import defaultdict

    n, m, s = map(int, readline().split())
    s_max = 0

    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = map(int, readline().split())
        u, v = u - 1, v - 1
        edge[u].append((v, a, b))
        edge[v].append((u, a, b))
        s_max += a

    exchange = [[0] * 2 for _ in range(n)]
    for i in range(n):
        c, d = map(int, readline().split())
        exchange[i][0], exchange[i][1] = c, d

    s_start = min(s, s_max)

    hq = []
    heapq.heappush(hq, (0, s_start, 0))
    dist = [[INF] * (s_max + 1) for _ in range(n)]

    while hq:
        cost, s_cur, u = heapq.heappop(hq)

        s_rate, s_time = exchange[u][0], exchange[u][1]
        s_next = s_cur + s_rate
        s_next = min(s_next, s_max)
        if cost + s_time < dist[u][s_next]:
            heapq.heappush(hq, (cost + s_time, s_next, u))
            dist[u][s_next] = cost + s_time

        for v, a, b in edge[u]:
            if s_cur >= a and cost + b < dist[v][s_cur - a]:
                heapq.heappush(hq, (cost + b, s_cur - a, v))
                dist[v][s_cur - a] = cost + b

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        adj: adj[a]=[(b,dist)]//なんとなく
    """

    def __init__(self, start, num_node, adj):
        """
        adj: adj[a]=[(b,dist)]
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.adj= adj
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        Qには、dist*N+nodeを入れることで高速化
        """
        Q = []
        heapq.heappush(Q, self.start_node)
        while Q:
            dist_to_node, node = divmod(heapq.heappop(Q),self.num_node)
            
            if self.dist[node] < dist_to_node:
                continue

            
            for nex,weight in self.adj[node]:
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, cand*self.num_node+nex)

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]
    def get_path(self,dst):
        """
        startからdstまでのpathをlistでreturn
        valifyしてないので怪しい
        """
        cur=dst
        ret=[cur]
        while cur!=self.start_node:
            cur=self.prev[cur]
            ret.append(cur)
        return list(reversed(ret))
N,M,S = map(int,input().split())
edges=[list(map(int,input().split())) for _ in range(M)]
C=[list(map(int,input().split())) for _ in range(N)]

max_c=2501


def toId(node,cur):
    return node*max_c+cur

def revId(id):
    return id//max_c,id%max_c


states=N*max_c
adj=[[] for _ in range(states)]


for a,b,c,d in edges:
    a-=1
    b-=1
    for cc in range(max_c-c):
        adj[toId(a,cc+c)].append((toId(b,cc),d))
        adj[toId(b,cc+c)].append((toId(a,cc),d))

for i,(c,d) in enumerate(C):
    for cc in range(max_c-c):
        adj[toId(i,cc)].append(((toId(i,cc+c),d)))






    
S=min(S,max_c-1)
start=toId(0,S)

D=Dijkstra(start,states,adj)
D.calc_dist()
for i in range(1,N):
    ans=float("inf")
    path=None
    for cc in range(max_c):
        if ans>D.get_dist(toId(i,cc)):
            ans=D.get_dist(toId(i,cc))
            path=D.get_path(toId(i,cc))
    print(ans)

Solution (Python):
import heapq
import sys
from collections import defaultdict
readline = sys.stdin.readline

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

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

visited = defaultdict(int)
ans = [-1] * n
count = 0

q = [(0, 0, s)]
while q:
    t, i, s = heapq.heappop(q)
    if visited[(i, s)]:
        continue
    visited[(i, s)] = 1
    if ans[i] == -1:
        ans[i] = t
        count += 1
        if count == n:
            break

    if s <= 2500:
        tc, td = ms[i]
        heapq.heappush(q, (t + td, i, s + tc))
    for ni, a, b in ls[i]:
        if not visited[(ni, s - a)] and s >= a:
            heapq.heappush(q, (t + b, ni, s - a))

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

Solution (Python):
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [[0, min(S, MAX), 0, -1]]
    ans = [None] * N
    remain = N
    while len(q) and remain:
        time, coin, cur, prev = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
            remain -= 1
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, [time + D[cur], min(coin + C[cur], MAX), cur, cur])
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if nxt != prev and dcost <= coin:
                heappush(q, [time + dtime, coin - dcost, nxt, cur])
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
S = min(S, N*50)
query = [[[] for _ in range(N*50+1)] for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    for coin in range(a, N*50+1):
        query[u-1][coin].append((v-1, a, b))
        query[v-1][coin].append((u-1, a, b))
for i in range(N):
    c, d = mapint()
    for coin in range(N*50+1):
        query[i][coin].append((i, -c, d))

inf = 10**18
dp = [[inf]*(N*50+1) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    qlis = query[now][coin]
    for nx, a, b in qlis:
        if 0<=coin-a:
            coin = min(coin, N*50+a)
            if t+b<dp[nx][coin-a]:
                dp[nx][coin-a] = t+b
                heapq.heappush(queue, (t+b, nx, coin-a))

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

Solution (Python):
import sys
from heapq import *
I=sys.stdin.readlines()
N,M,S=map(int,I[0].split())
S=min(S,2499)
G=[[] for i in range(2500*N)]
u,v,a,b=0,0,0,0
for i in range(M):
  u,v,a,b=map(int,I[i+1].split())
  u,v=u-1,v-1
  for j in range(a,2500):
    G[u+j*N].append((v+(j-a)*N,b))
    G[v+j*N].append((u+(j-a)*N,b))
for i in range(N):
  a,b=map(int,I[M+i+1].split())
  for j in range(a,2500):
    G[i+(j-a)*N].append((i+j*N,b))
D=[0]*(2500*N)
INF=10**15
def ijk(s):
  global D,INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(S*N)
for i in range(1,N):
  print(min(D[i::N]))

Solution (Python):
import collections

n,m,s=map(int,input().split())
g=[[] for _ in range(n+1)]
dic={}
for _ in range(m):
  u,v,a,b=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
  dic[(u,v)]=(a,b)
  dic[(v,u)]=(a,b)
arr=[[0,0]]+[list(map(int,input().split())) for _ in range(n)]
cost=[[10**18]*2501 for _ in range(n+1)]
for i in range(min(2500,s)+1):
  cost[1][i]=0
q=collections.deque()
q.append(1)
while len(q)!=0:
  v=q.popleft()
  c,d=arr[v]
  for i in range(c,2501):
    cost[v][i]=min(cost[v][i],cost[v][i-c]+d)
  for u in g[v]:
    a,b=dic[(v,u)]
    flag=False
    for i in range(a,2501):
      if cost[u][i-a]>cost[v][i]+b:
        cost[u][i-a]=cost[v][i]+b
        flag=True
    if flag==True:
      q.append(u)

for i in range(2,n+1):
  print(min(cost[i]))

Solution (Python):
import sys
import heapq
def dijkstra(s,es):
    INF=sys.maxsize
    cs=[INF]*len(es)
    cs[s],hq=0,[]
    heapq.heapify(hq)
    heapq.heappush(hq,(cs[s],s))
    while hq:
        d,v=heapq.heappop(hq)
        if cs[v]<d:continue
        for t,b in es[v]:
            if cs[t]>cs[v]+b:
                cs[t]=cs[v]+b
                heapq.heappush(hq,(cs[t],t))
    return cs
def nwc(n,c):
    MAX_COINS=2500
    return (MAX_COINS+1)*n+c
def main():
    MAX_COINS=2500
    N,M,S=tuple(map(int,sys.stdin.readline().split()))
    S=S if S<MAX_COINS else MAX_COINS
    es=[[] for _ in range(N*(MAX_COINS+1))]
    for _ in range(M):
        u,v,a,b=tuple(map(int,sys.stdin.readline().split()))
        u,v=u-1,v-1
        for c in range(a,MAX_COINS+1):
            es[nwc(u,c)].append((nwc(v,c-a),b))
            es[nwc(v,c)].append((nwc(u,c-a),b))
    for n in range(N):
        c,d=tuple(map(int,sys.stdin.readline().split()))
        c=c if c<MAX_COINS else MAX_COINS
        for i in range(0,MAX_COINS-c+1):es[nwc(n,i)].append((nwc(n,i+c),d))
    cs=dijkstra(nwc(0,S),es)
    for n in range(1,N):print(min(cs[n*(MAX_COINS+1):(n+1)*(MAX_COINS+1)]))
if __name__=='__main__':main()

Solution (Python):

import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []

    def p(q, u, m, alt):
        if m >= 0 and d[u][m] > alt:
            d[u][m] = alt
            heapq.heappush(q, (d[u][m], (u, m)))

    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        p(q, u, min(MA, s+c), d[u][s] + dd)

        for v in g[u]:
            a, b = g[u][v]
            p(q, v, s-a, b + d[u][s])

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Solution (Python):

import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []

    def p(q, u, m, alt):
        if m >= 0 and d[u][m] > alt:
            d[u][m] = alt
            heapq.heappush(q, (d[u][m], (u, m)))

    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            p(q, u, min(MA, s+c), d[u][s] + dd)

        for v in g[u]:
            a, b = g[u][v]
            p(q, v, s-a, b + d[u][s])

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Solution (Python):

import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []

    def p(q, u, m, alt):
        if m >= 0 and d[u][m] > alt:
            d[u][m] = alt
            heapq.heappush(q, (d[u][m], (u, m)))

    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            m = min(MA, s+c)
            alt = d[u][s] + dd
            p(q, u, m, alt)

        for v in g[u]:
            a, b = g[u][v]
            alt = b + d[u][s]
            m = s - a
            p(q, v, m, alt)

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Solution (Python):

import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []
    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            m = min(MA, s+c)
            alt = d[u][s] + dd
            if d[u][m] > alt:
                d[u][m] = alt
                heapq.heappush(q, (d[u][m], (u, m)))
        for v in g[u]:
            a, b = g[u][v]
            alt = b + d[u][s]
            m = s - a
            if m >= 0 and d[v][m] > alt:
                d[v][m] = alt
                heapq.heappush(q, (d[v][m], (v, m)))

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappush, heappop
def resolve():
    INF = float('inf')
    maxMoney = 2502

    def Dijkstra(g):
        ans = {}
        
        dp = [[INF] * (maxMoney + 1) for _ in range(N)]
        
        hq = []
        heappush(hq, (0, 0, min(S, maxMoney)))
        while hq:
            t, v, s = heappop(hq)
            if t > dp[v][s]:
                continue
            if v not in ans:
                ans[v] = t
                if len(ans) == N:
                    break

            
            if s < maxMoney:
                c, d = CD[v]
                new_s = min(s + c, maxMoney)
                new_t = t + d
                if new_t < dp[v][new_s]:
                    dp[v][new_s] = new_t
                    heappush(hq, (new_t, v, new_s))

            
            for nv, cost, time in G[v]:
                
                if s < cost:
                    continue
                
                new_s = s - cost
                new_t = t + time
                if new_t < dp[nv][new_s]:
                    dp[nv][new_s] = new_t
                    heappush(hq, (new_t, nv, new_s))
        return ans

    N, M, S = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, coin, tm = map(int, input().split())
        u, v = u - 1, v - 1
        G[u].append((v, coin, tm))
        G[v].append((u, coin, tm))
    CD = [list(map(int, input().split())) for _ in range(N)]

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


if __name__ == "__main__":
    resolve()