Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    Q = int(input())
    ST = [tuple(map(int, input().split())) for _ in range(Q)]

    dist = [[INF] * N for _ in range(N)]
    fuel = [[INF] * N for _ in range(N)]

    for i in range(N):
        dist[i][i] = 0
        fuel[i][i] = 0

    for fr, to, cost in ABC:
        if cost > L:
            continue
        fr -= 1
        to -= 1
        dist[fr][to] = cost
        dist[to][fr] = cost

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = dist[i][k] + dist[k][j]
                dist[i][j] = min(dist[i][j], d)
                if d <= L:
                    fuel[i][j] = 1

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

    for start, end in ST:
        print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

sol()

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    Q = int(input())
    ST = [tuple(map(int, input().split())) for _ in range(Q)]

    dist = [[INF] * N for _ in range(N)]
    fuel = [[INF] * N for _ in range(N)]

    for i in range(N):
        dist[i][i] = 0
        fuel[i][i] = 0

    for fr, to, cost in ABC:
        if cost > L:
            continue
        fr -= 1
        to -= 1
        dist[fr][to] = cost
        dist[to][fr] = cost

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = dist[i][k] + dist[k][j]
                dist[i][j] = min(dist[i][j], d)
                if d <= L:
                    fuel[i][j] = 1

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

    ans = [fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1 for start, end in ST]
    for a in ans:
        print(a)

sol()

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    Q = int(input())
    ST = [tuple(map(int, input().split())) for _ in range(Q)]

    dist = [[INF] * N for _ in range(N)]
    fuel = [[INF] * N for _ in range(N)]

    for i in range(N):
        dist[i][i] = 0
        fuel[i][i] = 0

    for fr, to, cost in ABC:
        if cost > L:
            continue
        fr -= 1
        to -= 1
        dist[fr][to] = cost
        dist[to][fr] = cost

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = dist[i][k] + dist[k][j]
                dist[i][j] = min(dist[i][j], d)
                if d <= L:
                    fuel[i][j] = 1

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

    ans = []
    for start, end in ST:
        start -= 1
        end -= 1
        ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

    print(*ans, sep='\n')


sol()



Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]
INF = float('inf')

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            dist[i][j] = min(dist[i][j], d)
            if d <= L:
                fuel[i][j] = 1

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

ans = []
for start, end in ST:
    start -= 1
    end -= 1
    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]
INF = float('inf')

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            dist[i][j] = min(dist[i][j], d)
            if d <= L:
                fuel[i][j] = 1

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

ans = []
for start, end in ST:
    start -= 1
    end -= 1
    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
INF = float('inf')

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for _ in range(M):
    fr, to, cost = map(int, input().split())
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            dist[i][j] = min(dist[i][j], d)
            if d <= L:
                fuel[i][j] = 1

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

Q = int(input())
ans = []
for _ in range(Q):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
INF = float('inf')

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

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])
            if dist[i][j] <= L:
                fuel[i][j] = 1

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

Q = int(input())
ans = []
for _ in range(Q):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
INF = float('inf')

dist = [[INF] * N for _ in range(N)]

for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for i in range(N):
    dist[i][i] = 0

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])

fuel = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dist[i][j] <= L:
            fuel[i][j] = 1

for i in range(N):
    fuel[i][i] = 0

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

Q = int(input())
ans = []
for _ in range(Q):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
INF = float('inf')

dist = [[INF] * N for _ in range(N)]

for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

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])

fuel = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dist[i][j] <= L:
            fuel[i][j] = 1

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

Q = int(input())
ans = []
for _ in range(Q):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges[fr].append((to, cost))
        edges[to].append((fr, cost))

    Q = int(input())
    ans = []
    for _ in range(Q):
        start, end = map(int, input().split())
        start -= 1
        end -= 1

        que = [(0, start, L, 0)]
        cntList = [INF] * N
        while que:
            cnt, now, fuel, var = heappop(que)

            if cntList[now] <= cnt:
                continue

            cntList[now] = cnt

            for to, cost in edges[now]:
                c = cnt
                f = fuel
                v = var
                if f - cost < 0:
                    if v == 0:
                        continue
                    c += 1
                    f = L
                    v -= 1
                heappush(que, (c, to, f - cost, v + 1))

        if cntList[end] == INF:
            ans.append(-1)
        else:
            ans.append(cntList[end])

    print(*ans, sep='\n')

sol()

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)