Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

    N, M, L = map(int, input().split())

    dist = [[inf] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        dist[A][B] = dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(
                    dist[i][j],
                    dist[i][k] + dist[k][j]
                )

    g = [[inf] * N for _ in range(N)]  # 到達に必要な補充回数
    for A in range(N):
        for B in range(N):
            if dist[A][B] <= L:
                g[A][B] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(
                    g[i][j],
                    g[i][k] + g[k][j]
                )

    Q = int(input())
    for _ in range(Q):
        s, t = (int(x) - 1 for x in input().split())
        d = g[s][t]
        if d == inf:
            print(-1)
        else:
            print(d - 1)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

input = sys.stdin.readline

inf = 300 * (10 ** 9) + 10

n, m, max_tank = map(int, input().split())

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    if c > max_tank:
        continue
    # 燃料不足で通過できない

    a -= 1
    b -= 1

    dist[a][b] = c
    dist[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

g = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= max_tank:
            g[i][j] = 0

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j] + 1)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(-1 if g[s][t] == inf else g[s][t])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

input = sys.stdin.readline

n, m, max_tank = map(int, input().split())

g = tuple(set() for _ in range(n))
for _ in range(m):
    a, b, c = map(int, input().split())
    if c > max_tank:
        continue
    # 燃料不足で通過できない

    a -= 1
    b -= 1
    g[a].add((b, c))
    g[b].add((a, c))
    # 隣接リスト、(行き先、コスト)

inf = n + 10

memo = [None] * n

q = int(input())

for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1

    if not g[t]:
        print(-1)
        continue
    # ゴールに接続する辺がない場合

    d = [inf] * n
    remains = [0] * n

    d[s] = 0
    remains[s] = max_tank

    if memo[s] is not None:
        if memo[s][t] >= inf:
            print(-1)
        else:
            print(memo[s][t])

    else:
        dq = deque()
        dq.append((s, max_tank, 0, -1))

        ans = inf
        while dq:
            v, tank, take, parent = dq.popleft()
            if (d[v] < take) or (d[v] == take and remains[v] > tank):
                continue

            for u, c in g[v]:
                if u == parent:
                    continue
                if c > tank:
                    if (d[u] > take + 1) or (d[u] == take + 1 and remains[u] < max_tank - c):
                        d[u] = take + 1
                        remains[u] = max_tank - c
                        dq.append((u, max_tank - c, take + 1, v))
                else:
                    if (d[u] > take) or (d[u] == take and remains[u] < tank - c):
                        d[u] = take
                        remains[u] = tank - c
                        dq.appendleft((u, tank - c, take, v))

        memo[s] = d

        if d[t] >= inf:
            print(-1)
        else:
            print(d[t])


Fixed submission:
import sys

input = sys.stdin.readline

inf = 300 * (10 ** 9) + 10

n, m, max_tank = map(int, input().split())

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    if c > max_tank:
        continue
    # 燃料不足で通過できない

    a -= 1
    b -= 1

    dist[a][b] = c
    dist[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

g = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= max_tank:
            g[i][j] = 0

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j] + 1)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(-1 if g[s][t] == inf else g[s][t])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

input = sys.stdin.readline

n, m, max_tank = map(int, input().split())

g = tuple(set() for _ in range(n))
for _ in range(m):
    a, b, c = map(int, input().split())
    if c > max_tank:
        continue
    # 燃料不足で通過できない

    a -= 1
    b -= 1
    g[a].add((b, c))
    g[b].add((a, c))
    # 隣接リスト、(行き先、コスト)

inf = n + 10

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1

    if not g[t]:
        print(-1)
        continue
    # ゴールに接続する辺がない場合

    d = [inf] * n
    remains = [0] * n

    d[s] = 0
    remains[s] = max_tank

    dq = deque()
    dq.append((s, max_tank, 0, -1))
    while dq:
        v, tank, take, parent = dq.popleft()
        if (d[v] < take) or (d[v] == take and remains[v] > tank):
            continue

        if v == t:
            break
            
        for u, c in g[v]:
            if u == parent:
                continue
            if c > tank:
                if (d[u] > take + 1) or (d[u] == take + 1 and remains[u] < max_tank - c):
                    d[u] = take + 1
                    remains[u] = max_tank - c
                    dq.append((u, max_tank - c, take + 1, v))
            else:
                if (d[u] > take) or (d[u] == take and remains[u] < tank - c):
                    d[u] = take
                    remains[u] = tank - c
                    dq.appendleft((u, tank - c, take, v))

    if d[t] == inf:
        print(-1)
    else:
        print(d[t])


Fixed submission:
import sys

input = sys.stdin.readline

inf = 300 * (10 ** 9) + 10

n, m, max_tank = map(int, input().split())

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    if c > max_tank:
        continue
    # 燃料不足で通過できない

    a -= 1
    b -= 1

    dist[a][b] = c
    dist[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

g = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= max_tank:
            g[i][j] = 0

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j] + 1)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(-1 if g[s][t] == inf else g[s][t])