Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

class RMQ:
    def __init__(self, size):
        n = 1
        while n < size:
            n <<= 1
        self.n = n
        self.data = [float('inf')] * (2*n-1)
        self.ix = [-1] * (2*n-1)

    # change the value of the ith element to x
    def update(self, i, x):
        i += self.n-1  # the leaf
        self.data[i] = x
        self.ix[i] = i-(self.n-1)
        while i > 0:
            i = (i-1)//2
            vl = self.data[i*2+1]
            vr = self.data[i*2+2]
            if vl < vr:
                self.data[i] = vl
                self.ix[i] = self.ix[i*2+1]
            else:
                self.data[i] = vr
                self.ix[i] = self.ix[i*2+2]

    # return the minimum value in the range [a, b)
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n)

    # i is the index of the node, and it corresponds to the range [l, r)
    def _query(self, a, b, i, l, r):
        if r == -1:
            r = self.n

        # if no overlap
        if r <= a or b <= l:
            return float('inf')

        # if [a, b) contains whole [l, r)
        if a <= l and r <= b:
            return self.data[i]

        m = (l+r)//2
        vl = self._query(a, b, i*2+1, l, m)
        vr = self._query(a, b, i*2+2, m, r)
        return min(vl, vr)

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    MAX = 10001
    AB = [[None] * N for _ in range(N)]
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    rmq = RMQ(N*MAX)
    for i in range(N*MAX):
        rmq.update(i, dist[i])
    for v in range(1, N):
        print(rmq.query(v*MAX, (v+1)*MAX))

main()

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    AB = [[None] * N for _ in range(N)]
    s = 0
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
        s += A
    MAX = s + 1
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    for v in range(1, N):
        print(min(dist[v*MAX:(v+1)*MAX]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

N, M, S = map(int, input().split())
MAX = 10000
AB = [[None] * N for _ in range(N)]
for _ in range(M):
    U, V, A, B = map(int, input().split())
    U -= 1
    V -= 1
    AB[U][V] = AB[V][U] = (A, B)
CD = [tuple(map(int, input().split())) for _ in range(N)]
edges = [[] for _ in range(N*(MAX+1))]
for v in range(N):
    C, D = CD[v]
    for i in range(MAX):
        edges[v*(MAX+1)+i].append((min(v*(MAX+1)+i+C, (v+1)*(MAX+1)-1), D))
for u in range(N-1):
    for v in range(u+1, N):
        if not AB[u][v]:
            continue
        A, B = AB[u][v]
        for i in range(A, MAX+1):
            edges[u*(MAX+1)+i].append((v*(MAX+1)+i-A, B))
            edges[v*(MAX+1)+i].append((u*(MAX+1)+i-A, B))
dist = dijkstra(edges, N*(MAX+1), min(S, MAX))
for v in range(1, N):
    print(min(dist[v*(MAX+1):(v+1)*(MAX+1)]))

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    AB = [[None] * N for _ in range(N)]
    s = 0
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
        s += A
    MAX = s + 1
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    for v in range(1, N):
        print(min(dist[v*MAX:(v+1)*MAX]))
main()