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

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
pq = PriorityQueue()
pq.put((cost, x), block=False)
ans = [1000000000000000]*(n+1)
while not pq.empty():
    cost, x = pq.get_nowait()
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    ans[p] = min(ans[p], cost)
    c, d = town[p]
    if m <= 2501:
        pq.put((cost+d, (p, m+c)), block=False)
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            pq.put((cost+b, (q, m-a)), block=False)
for i in range(2, n+1):
    print(ans[i])

Fixed submission:
from queue import PriorityQueue
from collections import defaultdict
from heapq import heappush, heappop

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
heap = []
heappush(heap, (cost, x))
ans = [None]*(n+1)
check = 0
while len(heap) > 0:
    cost, x = heappop(heap)
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    if ans[p] is None:
        ans[p] = cost
        check += 1
        if check >= n:
            break
    c, d = town[p]
    if m <= 2501:
        heappush(heap, (cost+d, (p, m+c)))
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            heappush(heap, (cost+b, (q, m-a)))
for i in range(2, n+1):
    print(ans[i])

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

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
pq = PriorityQueue()
pq.put((cost, x))
ans = [1000000000000000]*(n+1)
while not pq.empty():
    cost, x = pq.get()
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    ans[p] = min(ans[p], cost)
    c, d = town[p]
    if m <= 2501:
        pq.put((cost+d, (p, m+c)))
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            pq.put((cost+b, (q, m-a)))
for i in range(2, n+1):
    print(ans[i])

Fixed submission:
from queue import PriorityQueue
from collections import defaultdict
from heapq import heappush, heappop

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
heap = []
heappush(heap, (cost, x))
ans = [None]*(n+1)
check = 0
while len(heap) > 0:
    cost, x = heappop(heap)
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    if ans[p] is None:
        ans[p] = cost
        check += 1
        if check >= n:
            break
    c, d = town[p]
    if m <= 2501:
        heappush(heap, (cost+d, (p, m+c)))
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            heappush(heap, (cost+b, (q, m-a)))
for i in range(2, n+1):
    print(ans[i])