Buggy python submission (verdict: Time Limit Exceeded):
class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])

n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [RangeMinimumQuery(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur].query(money, max_money+1) <= time:
        continue
    state[cur].update(money, time)
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to].query(money-a, max_money+1) <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print(state[i].query(0, max_money+1))


Fixed submission:
max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [[float("inf")]*(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur][money] <= time:
        continue
    state[cur][money] = time
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            if state[cur][n_money] < n_time:
                break
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to][money-a] <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print(min(state[i]))

Fixed submission:
max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [[float("inf")]*(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,-s,0)]
while heap:
    time, money, cur = heappop(heap)
    money = -money
    if state[cur][money] <= time:
        continue
    state[cur][money] = time
    n_money = money
    n_time = time
    f = False
    for i in range(10000):
        n_money += cd[cur][0]
        n_time += cd[cur][1]
        if n_money > max_money:
            n_money = max_money
            f = True
        if state[cur][n_money] < n_time:
            break
        heappush(heap, (n_time, -n_money, cur))
        if f:
            break
    for to, a,b in G[cur]:
        if money < a or state[to][money-a] <= time+b:
            continue
        heappush(heap, (time+b, -(money-a), to))

for i in range(1, n):
    print(min(state[i]))

Fixed submission:
max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)