Buggy python submission (verdict: Time Limit Exceeded):
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))

    
dist = [INF] * (3001 * n)
dist[min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * 3001 + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v * 3001 + tmp + cc] > dist[v * 3001 + tmp] + dd:
                dist[v * 3001 + tmp + cc] = dist[v * 3001 + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * 3001 + g] + time < dist[nxt_v * 3001 + g - cost]:
                dist[nxt_v * 3001 + g - cost] = dist[v * 3001 + g] + time
                heapq.heappush(q, (dist[nxt_v * 3001 + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * 3001:(i + 1) * 3001]))


Fixed submission:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 3001 for i in range(n)]
dist[0][min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v][gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v][tmp + cc] > dist[v][tmp] + dd:
                dist[v][tmp + cc] = dist[v][tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

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


Fixed submission:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 3001 for i in range(n)]
dist[0][min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v][gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v][tmp + cc] > dist[v][tmp] + dd:
                dist[v][tmp + cc] = dist[v][tmp] + dd
                r.append(tmp)
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

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


Fixed submission:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 5051 for i in range(n)]
dist[0][min(s, 5050)] = 0

q = [(0, min(s, 5050), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)
    if dist[v][gin] < d:
        continue
    tmp = gin
    cc, dd = change[v]
    while True:
        if tmp + cc <= 5050:
            dist[v][tmp + cc] = min(dist[v][tmp + cc],  dist[v][tmp] + dd)
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in range(5051):
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

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

Fixed submission:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))