Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Fixed submission:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Fixed submission:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

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

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Fixed submission:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

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

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    for neighbor, a, b in connect[city]:
        if coin - a >= 0:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Fixed submission:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

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

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))