Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (t + b, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c = ccc[v]
    d = ddd[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    c = ccc[v]
    d = ddd[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    while ts < 2500:
        ts += ccc[v]
        tt += ddd[v]
        if (ts, v) not in visited:
            heappush(q, (tt, ts, v))
        else:
            break

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    while ts < 2500:
        ts += ccc[v]
        tt += ddd[v]
        if (ts, v) not in visited:
            heappush(q, (tt, ts, v))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    while ts < 2500:
        ts += ccc[v]
        tt += ddd[v]
        nk = (tt, ts, v)
        if nk not in visited:
            heappush(q, (tt, ts, v))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    while ts < 2500:
        ts += ccc[v]
        tt += ddd[v]
        nk = (tt, ts, v)
        if nk not in visited:
            heappush(q, (tt, ts, v))

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


Fixed submission:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

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