Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

import sys
input = sys.stdin.readline

INF = float("INF")

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

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

for _ in range(M):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1-1, v2-1
    cost[v1][v2] = w
    cost[v2][v1] = w

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

for i in range(N):
    for j in range(N):
        if cost[i][j] == 0:
            continue
        elif cost[i][j] <= L:
            cost[i][j] = 1
        else:
            cost[i][j] = INF

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

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


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):

INF = float("INF")


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

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

for _ in range(M):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1-1, v2-1
    cost[v1][v2] = w
    cost[v2][v1] = w

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

for i in range(N):
    for j in range(N):
        if cost[i][j] == 0:
            pass
        elif cost[i][j] <= L:
            cost[i][j] = 1
        else:
            cost[i][j] = INF

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

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


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

INF = float("INF")


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


if __name__ == '__main__':
    N, M, L = map(int, input().split())

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

    for _ in range(M):
        v1, v2, w = map(int, input().split())
        v1, v2 = v1-1, v2-1
        cost[v1][v2] = w
        cost[v2][v1] = w
    cost = run(cost, N)

    for i in range(N):
        for j in range(N):
            if cost[i][j] == 0:
                pass
            elif cost[i][j] <= L:
                cost[i][j] = 1
            else:
                cost[i][j] = INF
    cost = run(cost, N)

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


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


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


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    cost = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        cost[i][i] = 0

    for _ in range(M):
        v1, v2, w = map(int, input().split())
        v1, v2 = v1-1, v2-1
        if w <= L:
            cost[v1][v2] = w
            cost[v2][v1] = w
    cost = run(cost, N)

    for i in range(N):
        for j in range(N):
            if cost[i][j] == 0:
                pass
            elif cost[i][j] <= L:
                cost[i][j] = 1
            else:
                cost[i][j] = float('inf')
    cost = run(cost, N)

    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)


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


class Warshall(object):
    def __init__(self, n:int):
        self.cost = [[float('inf')] * n for _ in range(n)]

        self.n = n
        for i in range(n):
            self.cost[i][i] = 0

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.cost[v1][v2] = w
        if undirected:
            self.cost[v2][v1] = w

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


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    g = Warshall(N)
    g2 = Warshall(N)
    for _ in range(M):
        v1, v2, w = map(int, input().split())
        if w <= L:
            g.add_edge(v1 - 1, v2 - 1, w, undirected=True)
    g.run()

    for i in range(N):
        for j in range(N):
            if g.cost[i][j] <= L:
                g2.cost[i][j] = 1
    g2.run()

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


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


class Warshall(object):
    """ 全てのノード間の最短路を計算する """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

            for j in range(n):
                if i == j:
                    self.adjacency_dict[i][j] = 0
                else:
                    self.adjacency_dict[i][j] = float('inf')

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self):
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    self.adjacency_dict[i][j] = min(
                        self.adjacency_dict[i][j],
                        self.adjacency_dict[i][k] + self.adjacency_dict[k][j]
                    )


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    g = Warshall(N)
    g2 = Warshall(N)
    for _ in range(M):
        v1, v2, w = map(int, input().split())
        if w <= L:
            g.add_edge(v1 - 1, v2 - 1, w, undirected=True)
            # g2.add_edge(v1 - 1, v2 - 1, 1, undirected=True)
    g.run()

    for i in range(N):
        for j in range(N):
            if g.adjacency_dict[i][j] <= L:
                g2.adjacency_dict[i][j] = 1
    g2.run()

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


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


class Warshall(object):
    """ 全てのノード間の最短路を計算する """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

            for j in range(n):
                if i == j:
                    self.adjacency_dict[i][j] = 0
                else:
                    self.adjacency_dict[i][j] = float('inf')

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self):
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    self.adjacency_dict[i][j] = min(
                        self.adjacency_dict[i][j],
                        self.adjacency_dict[i][k] + self.adjacency_dict[k][j]
                    )


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    g = Warshall(N)
    g2 = Warshall(N)
    for _ in range(M):
        v1, v2, w = map(int, input().split())
        if w <= L:
            g.add_edge(v1 - 1, v2 - 1, w, undirected=True)
            g2.add_edge(v1 - 1, v2 - 1, 1, undirected=True)

    g.run()

    g2.adjacency_dict = g.adjacency_dict
    for i in range(N):
        for j in range(N):
            if g.adjacency_dict[i][j] <= L:
                g2.adjacency_dict[i][j] = 1
    g2.run()

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


Fixed submission:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)