Buggy python submission (verdict: Time Limit Exceeded):
N, M, L= map(int,input().split())
cost = [[float('inf')]*N for i in range(N)]

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

for _ in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(cost[i][k] + cost[k][j], cost[i][j])
for i in range(N):
    for j in range(N):
        if cost[i][j] > L:
            cost[i][j] = float('inf')
        else:
            cost[i][j] = 1

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

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


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L= map(int,input().split())
cost = [[float('inf')]*N for i in range(N)]

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

for _ in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(cost[i][k] + cost[k][j], cost[i][j])
for i in range(N):
    for j in range(N):
        if cost[i][j] > L:
            cost[i][j] = float('inf')
        else:
            cost[i][j] = 1

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

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


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        load[a-1].append([b-1,c])
        load[b-1].append([a-1,c])
cost =[[L*N+1]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                newc = (gas//L+1)*L+c
            else:
                newc = gas+c
            if newc < cost[i][t]:
                cost[i][t] = newc
                queue.append(t)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans > L*N:
        print(-1)
    else:
        print((ans-1)//L)
     


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[float('inf')]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[float("inf")]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == float('inf'):
        print(-1)
    else:
        print(o-1)
    


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Runtime Error):
import sys

imput = sys.stdin.readline
N,M,L = map(int,input().split())
road = [[float('inf')]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c

for i in range(N):
    for j in range(N):
        for k in range(N):
            road[i][j] = min(road[i][j],road[i][k]+road[k][j])
ans = [[float("inf")]*N for i in range(N)]
for i in range(N):
    ans[i][i] = 0
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
for i in range(N):
    for j in range(N):
        for k in range(N):
            ans[i][j] = min(ans[i][j],ans[i][k]+ans[k][j])
for i in range(int(input()):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == float('inf'):
        print(-1)
    else:
        print(o-1)
    


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        load[a-1].append([b-1,c])
        load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                newc = (gas//L+1)*L+c
            else:
                newc = gas+c
            if newc < cost[i][t]:
                cost[i][t] = newc
                queue.append(t)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


Fixed submission:
import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)