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():    
    import heapq
    
    n, m, s = map(int, input().split())
    if s >= 2500:
        s = 2499
    
    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = map(int, input().split())
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
    
    banks = []
    for i in range(n):
        coin, time = map(int, input().split())
        banks.append((coin, time))
    
    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    DP[0][s] = 0
    ans = [INF] * n
    
    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time
    
    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)
    
    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time >= DP[node][current_coin]:
            continue
    
        if current_time < ans[node]:
            ans[node] = current_time
    
        charge(node, current_coin, current_time)
    
        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)
    
    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    main()


def main():
    import heapq

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

    edges = [[] for _ in range(n)]
    max_cost = 0
    for _ in range(m):
        from_, to, cost, time = map(int, input().split())
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
        if cost > max_cost:
            max_cost = cost

    banks = []
    for i in range(n):
        coin, time = map(int, input().split())
        banks.append((coin, time))

    max_coin = max_cost * (n-1)
    if s > max_coin:
        s = max_coin

    INF = float('INF')
    DP = [[INF] * (max_coin+1) for _ in range(n)]
    DP[0][s] = 0

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin > max_coin:
            new_coin = max_coin
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for node in range(1, n):
        print(min(DP[node]))


if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Accepted