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 = map(int,input().split())
MAX_COST = 2500
S = min(S, MAX_COST)

G = [ [] for _ in range(N) ]
for i in range(M):
  u,v,s,t = map(int,input().split())
  u, v = u-1, v-1
  G[u].append([v, s, t])
  G[v].append([u, s, t])

change_rate, change_cost = [], []
for i in range(N):
  rate, cost = map(int,input().split())
  change_rate.append(rate)
  change_cost.append(cost)


dp = [ [float('inf')]*(MAX_COST+1) for _ in range(N) ]
dp[0][S] = 0


pq = [(0,0,S)]
while pq:
  time,node,silver = heapq.heappop(pq)

  
  next_silver = min(silver + change_rate[node], MAX_COST)
  next_time = time + change_cost[node]
  if next_time < dp[node][next_silver]:
    dp[node][next_silver] = next_time
    heapq.heappush(pq, (next_time, node, next_silver))

  for nei, ns, nt in G[node]:
    remain_silver = min(silver - ns, MAX_COST)
    if remain_silver < 0: continue

    next_time = time + nt
    if dp[nei][remain_silver] > next_time:
      dp[nei][remain_silver] = next_time
      heapq.heappush(pq, (next_time, nei, remain_silver))

for d in dp[1:]:
  print(min(d))

Solution (Python):
from heapq import heappush, heappop
import sys
n, m, s = map(int, input().split())
edges = list()
for _ in range(m):
  new_u, new_v, new_a, new_b = map(int, input().split())
  edges.append((new_u-1, new_v-1, new_a, new_b))
coins_range = (n-1)*max(edges,key=lambda item:item[2])[2]+1
c, d = list(), list()
for _ in range(n):
  new_c, new_d = map(int, input().split())
  c.append(new_c)
  d.append(new_d)
adjacency = {(i, j): [] for i in range(n) for j in range(coins_range)}
for (node, coins) in adjacency.keys():
  new_coins = coins+c[node]
  if new_coins<=coins_range-1:
    adjacency[(node, coins)].append(((node, coins+c[node]), (d[node])))
for edge in edges:
  node1, node2, cost, weight = edge
  for coins in range(cost, coins_range):
    adjacency[(node1, coins)].append(((node2, coins-cost), weight))
    adjacency[(node2, coins)].append(((node1, coins-cost), weight))
def dijkstra():
  while state_heap:
    distance, state = heappop(state_heap)
    if visited[state]:
      continue
    visited[state] = True
    for (new_state, weight) in adjacency[state]:
      if not visited[new_state]:
        distances[new_state] = min(distances[new_state], distance+weight)
        heappush(state_heap, (distances[new_state], new_state))
distances = {(i, j): float("inf") for i in range(n) for j in range(coins_range)}
initial_state = (0, min(s, coins_range-1))
distances[initial_state] = 0
state_heap = []
heappush(state_heap, (distances[initial_state], initial_state))
visited = {(i, j): False for i in range(n) for j in range(coins_range)}
dijkstra()
final_distances = [float("inf")]*n
for ((node, _), distance) in distances.items():
  final_distances[node] = min(final_distances[node], distance)
[print(distance) for distance in final_distances[1:]]

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


n,m,s = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(n)]

G = Graph()
for u,v,a,b in uvab:
    u-=1
    v-=1
    u*=2501
    v*=2501
    for i in range(2500,a-1,-1):
        G.add_edge(u+i,v+i-a,b)
        G.add_edge(v+i,u+i-a,b)
for i,(c,d) in enumerate(cd):
    i*=2501
    for j in range(2501-c):
        G.add_edge(i+j,i+j+c,d)

s = min(s,2500)
dist = Dijkstra(G, s)
for i in range(1,n):
    ans = 10 ** 18
    for j in range(2501):
        goal = i * 2501 + j
        D = dist.shortest_distance(goal)
        ans = min(ans, D)
    print(ans)

Solution (Python):
import collections
import heapq

INF = 10 ** 18
MAX_S = 50*50+5

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, cost, t): self.to, self.cost, self.t = to, cost, t

def main():
    N, M, S = ZZ()
    C, D = [0]*(N+1), [0]*(N+1)
    E = collections.defaultdict(list)
    dist = [[INF] * (MAX_S+1) for _ in range(N+1)]

    for _ in range(M):
        u, v, a, b = ZZ()
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    for i in range(1, N+1): C[i], D[i] = ZZ()

    S = min(S, MAX_S)
    dist[1][S] = 0

    que = list()
    heapq.heapify(que)
    heapq.heappush(que, [dist[1][S], 1, S])

    while que:
        x, v, s = heapq.heappop(que)
        if dist[v][s] < x: continue

        
        ns = min(s+C[v], MAX_S)
        if dist[v][ns] > x + D[v]:
            dist[v][ns] = x + D[v]
            heapq.heappush(que, [x+D[v], v, ns])

        
        for e in E[v]:
            if s - e.cost < 0: continue
            if dist[e.to][s-e.cost] > x + e.t:
                dist[e.to][s-e.cost] = x + e.t
                heapq.heappush(que, [x+e.t, e.to, s-e.cost])

    for i in range(2, N+1):
        output = INF
        for j in range(MAX_S+1): output = min(output, dist[i][j])
        print(output)
    return

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=min(S,MaxMoney)
    que=[]
    heappush(que,(cost,0,money)) 
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

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




if __name__=="__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
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)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] 
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()

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

    q = [(0, (0, S))]
    T = [-1] * N
    lenT = 0
    visited = set()
    MX = 50 * (N - 1)
    while q:
        t, V = heappop(q)
        v, s = V
        if T[v] < 0:
            T[v] = t
            lenT += 1
            if lenT >= N: break
        if V in visited: continue
        visited.add(V)
        for dt, ds, to in G1[v]:
            if s < ds: continue
            nV = (to, s - ds)
            if nV in visited: continue
            heappush(q, (t + dt, nV))
        c, d = G2[v]
        if s + c <= MX:
            heappush(q, (t + d, (v, s + c)))
    for i in range(1, N):
        print(T[i])

if __name__ == '__main__':
    main()

Solution (Python):


def solve():
    """解説実装"""
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  

    while len(que) != 0:
        t, v, s = heapq.heappop(que)

        

        
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))

        
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):


def solve():
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  
    

    while len(que) != 0:
        t, v, s = heapq.heappop(que)
        

        

        
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))
            

        
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))
                

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
import math
import fractions
from collections import deque
import itertools
import pprint
from heapq import *
N,M,S=map(int,input().split())
costtree={}                                                     
path=[[] for _ in range(N)]                                     
pathtime=[list(map(int,input().split())) for _ in range(M)]     
cointime=[list(map(int,input().split())) for _ in range(N)]     
needtime=[[float("inf") for _ in range(N)] for _ in range(N)]   
needcoin=[[float("inf") for _ in range(N)] for _ in range(N)]   
change=[]
for i in range(N):
    costtree[i]={}
    for j in range(2501):
        costtree[i][j]=float("inf")

for i in pathtime:
    u,v,a,b=i
    needcoin[u-1][v-1]=a
    needcoin[v - 1][u - 1] = a
    needtime[u-1][v-1]=b
    needtime[v - 1][u - 1] = b
    path[u-1].append(v-1)
    path[v-1].append(u-1)
for i in cointime:
    c,d=i
    change.append([c,d])                                        

costtree[0][min(S,2500)]=0                                      
q=[(0,0,min(S,2500))]                                           
heapify(q)


value=0
nextcoin=0
while len(q)>0:
    cost,u,coin=heappop(q)                                      
    if costtree[u][coin]<cost: continue                         
    if coin>0:                                                  
        if costtree[u][coin-1]>cost:                            
            costtree[u][coin-1]=cost                            
            heappush(q,[cost,u,coin-1])                         
    nextcoin=min(coin+change[u][0],2500)                        
    value=costtree[u][nextcoin]                                 
    if value>cost+change[u][1]:                                 
        costtree[u][nextcoin]=cost+change[u][1]                 
        heappush(q,[cost+change[u][1],u,nextcoin])              
    for j in path[u]:                                           
        nextcoin=coin-needcoin[u][j]                            
        if nextcoin>=0:                                         
            value=costtree[j][nextcoin]                         
            if value > cost + needtime[u][j]:                   
                costtree[j][nextcoin]=cost+needtime[u][j]       
                heappush(q,[cost+needtime[u][j],j,nextcoin])    
for i in range(1,N):
    print(costtree[i][0])

Solution (Python):
from collections import defaultdict
import heapq

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

max_money=max([a for _,_,a,_ in Edges])*N

Graph=defaultdict(lambda :[])





for u,v,a,b in Edges:
    u-=1;v-=1
    for cur_money in range(max_money+1):
        if cur_money-a<0:
            continue
        from_state_u=(u,cur_money)
        to_state_v=(v,cur_money-a)
        Graph[from_state_u].append((b,to_state_v))

        from_state_v=(v,cur_money)
        to_state_u=(u,cur_money-a)
        Graph[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(Exchanges):
    for cur_money in range(max_money+1):
        after_money=min(max_money,cur_money+c)
        from_state=(n,cur_money)
        to_state=(n,after_money)
        Graph[from_state].append((d,to_state))





start=(0,min(max_money,S))

Q=[(0,start)]

dist=defaultdict(lambda :float('inf'))
dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if dist[cur_state]<cur_time:
        continue
    for cost,next_state in Graph[cur_state]:
        next_time = cost+cur_time

        if dist[next_state]>next_time:
            dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    
    for a in range(max_money+1):
        state=(dest,a)
        ans=min(ans,dist[state])
    print(ans)

Solution (Python):
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q
    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Solution (Python):
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Solution (Python):


N,M,S=map(int,input().split())
graph={(i,j):[] for i in range(1,51) for j in range(2501)}
for _ in range(M):
    u,v,a,b=map(int,input().split())
    for i in range(a,2501):
        graph[(u,i)].append((b,(v,i-a)))
        graph[(v,i)].append((b,(u,i-a)))
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2501):
        graph[(i+1,j)].append((d,(i+1,min(2500,j+c))))

dist={(i,j):float("inf")  for i in range(1,51) for j in range(2501)}

dist[(1,min(2500,S))]=0
pq=[]
import heapq
heapq.heapify(pq)
heapq.heappush(pq,(0,(1,min(2500,S))))
while pq:
    mini_dis,node=heapq.heappop(pq)
    if dist[node]<mini_dis: continue
    for w,point in graph[node]:
        if dist[point]<w:continue
        newlen=dist[node]+w
        if newlen<dist[point]:
            heapq.heappush(pq,(newlen,point))
            dist[point]=newlen
for i in range(2,N+1):
    ans=10**20
    for j in range(2501):
        ans=min(ans,dist[(i,j)])
    print(ans)

Solution (Python):


N,M,S=map(int,input().split())
graph={(i,j):[] for i in range(1,51) for j in range(2501)}
for _ in range(M):
    u,v,a,b=map(int,input().split())
    for i in range(a,2501):
        graph[(u,i)].append((b,(v,i-a)))
        graph[(v,i)].append((b,(u,i-a)))
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2501):
        graph[(i+1,j)].append((d,(i+1,min(2500,j+c))))

dist={(i,j):float("inf")  for i in range(1,51) for j in range(2501)}

dist[(1,min(2500,S))]=0
pq=[]
import heapq
heapq.heapify(pq)
heapq.heappush(pq,(0,(1,min(2500,S))))
while pq:
    mini_dis,node=heapq.heappop(pq)
    if dist[node]<mini_dis: continue
    for w,point in graph[node]:
        if dist[point]<w:continue
        newlen=dist[node]+w
        if newlen<dist[point]:
            heapq.heappush(pq,(newlen,point))
            dist[point]=newlen
for i in range(2,N+1):
    ans=10**20
    for j in range(2501):
        ans=min(ans,dist[(i,j)])
    print(ans)

Solution (Python):
import heapq


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

graph=[[] for i in range(n)]

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

change=[]
for i in range(n):
    c,d=map(int,input().split())
    change.append((c,d))

A_max=max(A)
max_money=(n-1)*A_max

s=min(s,max_money)

width=max_money+1
N=n*width

system=[[] for i in range(N)]
for index in range(N):
    
    city=index//width
    
    money=index%width

    
    for next in graph[city]:
        
        if money>=next[1]:
            next_index=next[0]*width+(money-next[1])
            system[index].append((next[2],next_index))

    
    if money+change[city][0]<max_money:
        system[index].append((change[city][1],index+change[city][0]))
    else:
        system[index].append((change[city][1],max_money))


def dijkstra_heap(s,n,edge):
    
    scale=10**6

    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*scale+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(scale)]:
            continue
        v = minedge%(scale)
        d[v] = minedge//(scale)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*scale+e[1])
    return d


D=dijkstra_heap(s,N,system)
for i in range(1,n):
    ans=float('inf')
    for index in range(i*width,(i+1)*width):
        ans=min(ans,D[index])

    print(ans)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
 
INF = 10 ** 18
 
class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time
 
dp = []
h = []
 
def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))
 
def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)
 
    while h:
        
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)
 
 
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)]
 
es = [[] for i in range(n)]
max_s = 50 * (n-1)
 
for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))
 
dijkstra(n, es, cd, 0, min(max_s,s), max_s)
 
for i in range(1, n):
    print(min(dp[i]))

Solution (Python):


import sys, heapq, math
sys.setrecursionlimit(300000)


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(M):
        conns[U[i] - 1].append((V[i] - 1, A[i], B[i])) 
        conns[V[i] - 1].append((U[i] - 1, A[i], B[i])) 

    INF = float('inf')
    MAX_M = max(A) * N
    costs = [[None] * N for _ in range(N)]
    dp = [[INF] * (MAX_M + 1) for _ in range(N)]
    S = min(S, MAX_M)
    dp[0][S] = 0
    q = [(0, 0, S)] 
    while q:
        t, i, m = heapq.heappop(q)
        if dp[i][m] < t:
            continue

        if m + C[i] <= MAX_M:
            if t + D[i] < dp[i][m + C[i]]:
                dp[i][m + C[i]] = t + D[i]
                heapq.heappush(q, (t + D[i], i, m + C[i]))

        for j, c, d in conns[i]:
            if m >= c:
                if t + d < dp[j][m - c]:
                    dp[j][m - c] = t + d
                    heapq.heappush(q, (t + d, j, m - c))

    for i in range(1, N):
        tmp = INF
        for v in dp[i]:
            tmp = min(tmp, v)
        print(tmp)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    S = int(next(tokens))  
    U = [int()] * (M)  
    V = [int()] * (M)  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  
    D = [int()] * (N)  
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, S, U, V, A, B, C, D)

if __name__ == '__main__':
    main()