Problem: 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.

Submission attempts (in order):
def main():
    n, m, s = map(int, input().split())
    fr, al, bl, cl, dl = [dict() for _ in range(n)], [None]*m, [None]*m, [None]*n, [None]*n
    for i in range(m):
        u, v, a, b = map(int, input().split())
        fr[u-1][i] = v-1
        fr[v-1][i] = u-1
        al[i] = a
        bl[i] = b
    for i in range(n):
        c, d = map(int, input().split())
        cl[i] = c
        dl[i] = d
    if s > sum(al):
        dp = [10**13]*n
        dp[0] = 0
        for i in range(1, n):
            di = dp[i]
            for j, f in fr[i].items():
                time = dp[f] + bl[j]
                if di > time:
                    di = time
            dp[i] = di
            print(di)
    else:
        dp = [[10**13]*5001 for _ in range(n)]
        for i in range(s+1):
            dp[0][i] = 0
        for i in range(1, n):
            di = dp[i]
            for j, f in fr[i].items():
                
                #     additionalcoin = ccc*i
                
                
                cost = al[j]
                time = bl[j]
                cost2 = min(cost - cl[j], 5000)
                time2 = time + dl[j]
                for costi, timei in [[cost, time], [cost2, time2]]:
                    for si in range(5001-costi):
                        if si + costi >= 0:
                            di[si] = min(di[si], dp[f][si+costi] + timei)
            dp[i] = di
            print(min(di))
        
        
        
        
        
    
    

if __name__ == "__main__":
    main()


from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)




def main():
    n, m, s = map(int, input().split())
    edge = [[] for i in range(n)]
    cl, dl = [None]*n, [None]*n
    sa = 0
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append((v, b, a))
        edge[v].append((u, b, a))
        sa += a
    for i in range(n):
        c, d = map(int, input().split())
        cl[i] = c
        dl[i] = d
    dijkstra(n, s, edge, cl, dl)
        
        
    
def dijkstra(n, coin, edges, cl, dl):
    coin_max = 5000
    start = 0
    coin = min(coin, coin_max)
    d = [[10**15]*(coin_max+1) for _ in range(n)]
    d[start][coin] = 0
    priority_queue = []
    heappush(priority_queue, (0, start, coin))
    while priority_queue:
        cost_i, i, coin_i = heappop(priority_queue)
        if d[i][coin_i] < cost_i:
            continue
        supplied_coin = coin_i + cl[i]
        if supplied_coin <= coin_max and cost_i + dl[i] < d[i][supplied_coin]:
            d[i][supplied_coin] = cost_i + dl[i]
            heappush(priority_queue, (cost_i + dl[i], i, supplied_coin))
        for _to, _cost, _coin in edges[i]:
            ci = coin_i-_coin
            if coin_i >= _coin and d[_to][ci] > cost_i + _cost:
                d[_to][ci] = cost_i + _cost
                heappush(priority_queue, (cost_i + _cost, _to, ci))
    for i in d[1:]:
        print(min(i))
    
        

if __name__ == "__main__":
    main()

Verdicts: Runtime Error

Accepted