Buggy python submission (verdict: Runtime Error):
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline


n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=0)
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    print(int(ans))

Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
import heapq

n, m, full = map(int, input().split())
edges = [[]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])


def dijkstra(num_of_node, edge, start, limit):
    distance = [float('INF')] * num_of_node
    distance[start] = 0
    todo = []
    heapq.heapify(todo)
    heapq.heappush(todo, [0, start])

    while todo:
        d, node = heapq.heappop(todo)
        if d > limit:
            break
        L_edges[start][node] = 1
        for new_node, cost in edge[node]:
            if distance[new_node] > d + cost:
                distance[new_node] = d + cost
                heapq.heappush(todo, [d+cost, new_node])

            else:
                continue
    return


L_edges = [[float('INF')]*n for _ in range(n)]

for i in range(n):
    dijkstra(n, edges, i, full)

for i in range(n):
    L_edges[i][i] = float('INF')
G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

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

n, m, full = map(int, input().split())
edges = [[]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])


def dijkstra(num_of_node, edge, start, limit):
    distance = [float('INF')] * num_of_node
    reachable = []
    distance[start] = 0
    todo = []
    heapq.heapify(todo)
    heapq.heappush(todo, [0, start])

    while todo:
        d, node = heapq.heappop(todo)
        if d > limit:
            break
        reachable.append(node)
        for new_node, cost in edge[node]:
            if distance[new_node] > d + cost:
                distance[new_node] = d + cost
                heapq.heappush(todo, [d+cost, new_node])

            else:
                continue
    return reachable


L_edges = [[]*n for _ in range(n)]

for i in range(n):
    L_edges[i] = dijkstra(n, edges, i, full)

dist = [[float('INF')] * n for _ in range(n)]

for start in range(n):
    dist[start][start] = 0
    todo = deque([])
    todo.append([-1, start])

    while todo:
        d, node = todo.popleft()

        for new_node in L_edges[node]:
            if dist[start][new_node] > d + 1:
                dist[start][new_node] = d + 1
                todo.append([d+1, new_node])

            else:
                continue

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if ans == float('INF'):
        ans = -1
    print(ans)


Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

Buggy python submission (verdict: Runtime Error):
for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])


def dijkstra(num_of_node, edge, start, limit):
    distance = [float('INF')] * num_of_node
    reachable = []
    distance[start] = 0
    todo = []
    heapq.heapify(todo)
    heapq.heappush(todo, [0, start])

    while todo:
        d, node = heapq.heappop(todo)
        if d > limit:
            break
        reachable.append(node)
        for new_node, cost in edge[node]:
            if distance[new_node] > d + cost:
                distance[new_node] = d + cost
                heapq.heappush(todo, [d+cost, new_node])

            else:
                continue
    return reachable


L_edges = [[]*n for _ in range(n)]

for i in range(n):
    L_edges[i] = dijkstra(n, edges, i, full)

dist = [[float('INF')] * n for _ in range(n)]

for start in range(n):
    dist[start][start] = 0
    todo = deque([])
    todo.append([-1, start])

    while todo:
        d, node = todo.popleft()

        for new_node in L_edges[node]:
            if dist[start][new_node] > d + 1:
                dist[start][new_node] = d + 1
                todo.append([d+1, new_node])

            else:
                continue

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if ans == float('INF'):
        ans = -1
    print(ans)


Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

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

N, M, L = map(int, input().split())
routes = [[] for i in range(N+1)]

for i in range(M):
    a, b, c = map(int, input().split())
    routes[a].append([b, c])
    routes[b].append([a, c])


def bfs(start, goal, full_energy):
    todo = deque([])
    for to, cost in routes[start]:
        if full_energy - cost >= 0:
            todo.append([to, full_energy-cost, 0])

    while todo:
        now, power, charge = todo.popleft()
        if now == goal:
            return charge

        for nex, cost in routes[now]:
            if power - cost >= 0:
                todo.appendleft([nex, power-cost, charge])
            todo.append([nex, full_energy-cost, charge+1])
    return -1


memo = [[-2]*(N+1) for i in range(N+1)]
Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    if memo[s][t] == -2:
        count = bfs(s, t, L)
        memo[s][t], memo[t][s] = count, count
    print(memo[s][t])



Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

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

N, M, L = map(int, input().split())
routes = [[] for i in range(N+1)]

for i in range(M):
    a, b, c = map(int, input().split())
    routes[a].append([b, c])
    routes[b].append([a, c])


def bfs(start, goal, full_energy):
    todo = deque([])
    for to, cost in routes[start]:
        if full_energy - cost >= 0:
            todo.append([to, full_energy-cost, 0])

    while todo:
        now, power, charge = todo.popleft()
        if now == goal:
            return charge

        for nex, cost in routes[now]:
            if power - cost >= 0:
                todo.appendleft([nex, power-cost, charge])
            todo.append([nex, full_energy-cost, charge+1])
    return -1


Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    print(bfs(s, t, L))



Fixed submission:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))