Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, M, S = map(int, input().split())
Map = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

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

Q = []
heapq.heappush(Q, (0, 0, S)) # 今の時間、場所、持っているお金
Ans = [-1] * N
Ans[0] = 0
while -1 in Ans:
    time, where, money = heapq.heappop(Q)
    if Ans[where] == -1:
        Ans[where] = time
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        heapq.heappush(Q, (time + take, nex, money - cost))
    heapq.heappush(Q, (time + Exchange[where][1], where, money + Exchange[where][0]))


for a in Ans[1:]:
    print(a)

Fixed submission:
import heapq

N, M, S = map(int, input().split())
Map = [[] for _ in range(N)]
Ans = [[float('inf')] * 2500 for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

for i in range(N):
    c, d = map(int, input().split())
    Map[i].append((i, -c, d))

Q = []
heapq.heappush(Q, (0, 0, min(2499, S))) # 今の時間、場所、持っているお金
Ans[0][min(2499, S)] = 0
while Q:
    time, where, money = heapq.heappop(Q)
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        if Ans[nex][min(2499, money - cost)] > time + take:
            Ans[nex][min(2499, money - cost)] = time + take
            heapq.heappush(Q, (time + take, nex, money - cost))

for a in Ans[1:]:
    print(min(a))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, M, S = map(int, input().split())
Map = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

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

Q = []
heapq.heappush(Q, (0, 0, S)) # 今の時間、場所、持っているお金
Ans = [-1] * N
Ans[0] = 0
while -1 in Ans:
    time, where, money = heapq.heappop(Q)
    if Ans[where] == -1:
        Ans[where] = time
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        heapq.heappush(Q, (time + take, nex, money - cost))
    heapq.heappush(Q, (time + Exchange[where][1], where, money + Exchange[where][0]))


for a in Ans[1:]:
    print(a)

Fixed submission:
import heapq

N, M, S = map(int, input().split())
Map = [[] for _ in range(N)]
Ans = [[float('inf')] * 2500 for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

for i in range(N):
    c, d = map(int, input().split())
    Map[i].append((i, -c, d))

Q = []
heapq.heappush(Q, (0, 0, min(2499, S))) # 今の時間、場所、持っているお金
Ans[0][min(2499, S)] = 0
while Q:
    time, where, money = heapq.heappop(Q)
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        if Ans[nex][min(2499, money - cost)] > time + take:
            Ans[nex][min(2499, money - cost)] = time + take
            heapq.heappush(Q, (time + take, nex, money - cost))

for a in Ans[1:]:
    print(min(a))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N, M, S = map(int, input().split())
Route = [[]for i in range(N)]
for i in range(M):
    U, V, A, B = map(int, input().split())
    Route[U-1].append((V-1, -1 * A, B))
    Route[V-1].append((U-1, -1 * A, B))
for i in range(N):
    C, D = map(int, input().split())
    Route[i].append((i, C, D))

city_silver_time = [[-1 for j in range(3000)]for i in range(N)]
Q = deque()
if S >= 3000:
    S = 2999
city_silver_time[0][S] = 0
Q.append((0, S, 0))

while len(Q) > 0:
    now, have, time = Q.popleft()
    for i in range(len(Route[now])):
        next, cost, take = Route[now][i]
        if (have + cost < 0) or (have + cost >= 3000):
            continue
        elif city_silver_time[next][have + cost] == -1:
            city_silver_time[next][have + cost] = time + take
            Q.append((next, have + cost, time + take))
        elif city_silver_time[next][have + cost] > time + take:
            city_silver_time[next][have + cost] = time + take
            Q.append((next, have + cost, time + take))

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

Fixed submission:
import heapq

N, M, S = map(int, input().split())
Map = [[] for _ in range(N)]
Ans = [[float('inf')] * 2500 for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    Map[u].append((v, a, b))
    Map[v].append((u, a, b))

for i in range(N):
    c, d = map(int, input().split())
    Map[i].append((i, -c, d))

Q = []
heapq.heappush(Q, (0, 0, min(2499, S))) # 今の時間、場所、持っているお金
Ans[0][min(2499, S)] = 0
while Q:
    time, where, money = heapq.heappop(Q)
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        if Ans[nex][min(2499, money - cost)] > time + take:
            Ans[nex][min(2499, money - cost)] = time + take
            heapq.heappush(Q, (time + take, nex, money - cost))

for a in Ans[1:]:
    print(min(a))