Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*n
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

def Dijkstra(start):
    inf = float('inf')
    d = [[inf]*(A+1) for _ in range(n)]
    d[start][min(s,A)] = 0
    pq = [(0,start,min(s,A))]
    heapq.heapify(pq)
    while pq:
        dist,p,money = heapq.heappop(pq)
        while True:
            if money >= A:
                money = A
            for to,(cost,time) in path[p].items():
                if money < cost or d[to][money - cost] <= dist + time:continue
                d[to][money - cost] = dist + time
                heapq.heappush(pq, (d[to][money - cost],to,money - cost))
            if money == A:break
            money += C[p]
            dist += D[p]
        for to in path[p].keys():
            m = inf
            for i in range(A+1)[::-1]:
                m = min(m,d[to][i])
                d[to][i] = m
    return d

n,m,s = map(int,input().split())
path = [{} for _ in range(n)]
A = 0
for i in range(m):
    u,v,a,b = map(int,input().split())
    A += a
    u -= 1
    v -= 1
    path[u][v] = (a,b)
    path[v][u] = (a,b)
A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())
ans = Dijkstra(0)
for a in ans[1:]:
    print(min(a))


Fixed submission:
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = map(int,input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = map(int,input().split())
    # A += a
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in edge[i].items():
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print(min(ans[i*(A+1):i*(A+1)+A+1]))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*n
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

def Dijkstra(start):
    inf = float('inf')
    d = [[inf]*(A+1) for _ in range(n)]
    d[start][min(s,A)] = 0
    pq = [(0,start,min(s,A))]
    heapq.heapify(pq)
    while pq:
        dist,p,money = heapq.heappop(pq)
        while True:
            if money >= A:
                money = A
            for to,(cost,time) in path[p].items():
                if money < cost or d[to][money - cost] <= dist + time:continue
                d[to][money - cost] = dist + time
                heapq.heappush(pq, (d[to][money - cost],to,money - cost))
            if money == A:break
            money += C[p]
            dist += D[p]
        m = inf
    return d

n,m,s = map(int,input().split())
path = [{} for _ in range(n)]
A = 0
for i in range(m):
    u,v,a,b = map(int,input().split())
    A += a
    u -= 1
    v -= 1
    path[u][v] = (a,b)
    path[v][u] = (a,b)
A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())
ans = Dijkstra(0)
for a in ans[1:]:
    print(min(a))


Fixed submission:
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = map(int,input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = map(int,input().split())
    # A += a
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in edge[i].items():
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print(min(ans[i*(A+1):i*(A+1)+A+1]))