Problem:
 Score : 500 points    Problem Statement There are N towns numbered 1 to N and M roads. The i -th road connects Town A_i and Town B_i bidirectionally and has a length of C_i .  Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.  Process the following Q queries:   The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i . If Town t_i is unreachable, print -1 .       Constraints  All values in input are integers.  2 \leq N \leq 300  0 \leq M \leq \frac{N(N-1)}{2}  1 \leq L \leq 10^9  1 \leq A_i, B_i \leq N  A_i \neq B_i  \left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j )  \left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j )  1 \leq C_i \leq 10^9  1 \leq Q \leq N\left(N-1\right)  1 \leq s_i, t_i \leq N  s_i \neq t_i  \left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j )         Input Input is given from Standard Input in the following format:  N  M  L  A_1  B_1  C_1  :  A_M  B_M  C_M  Q  s_1  t_1  :  s_Q  t_Q       Output Print Q lines.  The i -th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i . If Town t_i is unreachable, the line should contain -1 instead.        Sample Input 1 3 2 5
1 2 3
2 3 3
2
3 2
1 3      Sample Output 1 0
1  To travel from Town 3 to Town 2 , we can use the second road to reach Town 2 without fueling the tank on the way.  To travel from Town 1 to Town 3 , we can first use the first road to get to Town 2 , full the tank, and use the second road to reach Town 3 .       Sample Input 2 4 0 1
1
2 1      Sample Output 2 -1  There may be no road at all.       Sample Input 3 5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5      Sample Output 3 0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int, input().split())
Map = np.full((N, N), 10**12, dtype='int64')
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Map[a][b] = c
    Map[b][a] = c
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
graph = floyd_warshall(Map).astype('int64')
graph[graph <= L] = 1
graph[graph > L] = 10**12
A = floyd_warshall(graph).astype('int64')
for s, t in Query:
    if A[s - 1][t - 1] >= 10**12:
        print(-1)
    else:
        print(int(A[s - 1][t - 1] - 1))

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

f=lambda:map(int,input().split())
N,M,L=f()
G=[[0]*N for _ in [0]*N]
for _ in [0]*M:
    a,b,c=f()
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    
csr=csr_matrix(G)

D=floyd_warshall(csr)
INF=float('inf')
G=[[INF]*N for _ in [0]*N]
for i in range(N):
    for j in range(N):
        if i!=j and D[i][j]<=L:
            G[i][j]=1
            G[j][i]=1
csr=csr_matrix(G)
res=floyd_warshall(csr)
Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s-1][t-1]
    print(int(r-1) if r<INF else -1)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

G = np.full((N, N), np.inf)
np.fill_diagonal(G, 0)
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c
D = floyd_warshall(G, directed=False)

G2 = np.full((N, N), np.inf)
np.fill_diagonal(G2, 0)
G2[D <= L] = 1
D2 = floyd_warshall(G2, directed=False)

Q = int(input())
for _ in range(Q):
    a, b = map(lambda x: int(x) - 1, input().split())
    if D2[a][b] == np.inf:
        print(-1)
    else:
        print(int(D2[a][b]) - 1)

Solution (Python):
import sys
import math
import heapq


def input():
    return sys.stdin.readline().rstrip()


def dijkstra(s, n, es, L):
    
    d = [10 ** 14 + 7] * n
    
    S = [(0, s)]
    
    heapq.heapify(S)
    used = [False] * n

    d[s] = 0

    while S:
        
        dg, v = heapq.heappop(S)
        if used[v] == True:
            continue
        used[v] = True
        for u, w in es[v]:
            if d[v] % L + w > L:
                cost = d[v] - d[v] % L + L + w
            else:
                cost = d[v] + w

            if d[u] > cost:
                d[u] = cost
                heapq.heappush(S, (d[u], u))

        
    return d


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

    dp = [[L+2]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] =0
    for i in range(M):
        x, y, z = map(int, input().split())
        if z > L:
            continue

        x = x - 1
        y = y - 1
        dp[x][y] =z
        dp[y][x]=z



    def warshal(ws,n):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    ws[i][j] =min(ws[i][j],ws[i][k]+ws[k][j])
        return ws

    ls =warshal(dp,N)
    for i in range(N):
        for j in range(N):
            if ls[i][j] <=L:
                ls[i][j] =1
            else:
                ls[i][j] =500
    vs = warshal(ls,N)

    Q =int(input())

    for j in range(Q):
        s,t =map(int,input().split())
        ans = vs[s - 1][t - 1] - 1
        if ans >=N:
            print(-1)
        else:
            print(vs[s-1][t-1]-1)





if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
inf = 1000
inf5 = 10**10
n, m, l = map(int, input().split())
graph = [[inf5] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c

inf = 1000


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


warshall_floyd(graph)

ans = [[inf] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] <= l:
            ans[i][j] = 1

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

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, L = map(int, readline().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, readline().split())
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    Q, *ST = map(int, read().split())

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

    H = [[INF] * N for _ in range(N)]
    for i in range(N - 1):
        for j in range(i + 1, N):
            if G[i][j] <= L:
                H[i][j] = H[j][i] = 1

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

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

    ans = [0] * Q
    for i, (s, t) in enumerate(zip(*[iter(ST)] * 2)):
        s -= 1
        t -= 1
        if H[s][t] == INF:
            ans[i] = -1
        else:
            ans[i] = H[s][t] - 1

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


if __name__ == '__main__':
    main()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,m,l = ma()
INF=10**15
cost = [[INF]*n for i in range(n)]
for i in range(m):
    a,b,c = ma();a-=1;b-=1
    cost[a][b]=c
    cost[b][a]=c

def wf(cost):
    l = len(cost[0])
    for k in range(l):
        for i in range(l):
            for j in range(l):
                cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
wf(cost)
rest = [[INF]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if cost[i][j]<=l:
            rest[i][j]=1
wf(rest)
q = ni()
for i in range(q):
    s,t = ma();s-=1;t-=1
    print(rest[s][t] -1) if rest[s][t] !=INF else print(-1)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, M, L = getNM()
edges = [getList() for i in range(M)]
Q = getN()
query = [getList() for i in range(Q)]

dist = [[float('inf')] * N for i in range(N)]
for i in range(N):
    dist[i][i] = 0
for i in range(M):
    a, b, c = edges[i]
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

def warshall_floyd(dist):
    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])
    return dist


warshall_floyd(dist)



dist_alta = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        if i == j:
            dist_alta[i][j] = 0
            continue
        if dist[i][j] <= L:
            dist_alta[i][j] = 1
            dist_alta[j][i] = 1

warshall_floyd(dist_alta)

for s, t in query:
    if dist_alta[s - 1][t - 1] == float('inf'):
        print(-1)
        continue
    print(dist_alta[s - 1][t - 1] - 1)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

for i in range(N):
  dist[i][i]=0
  
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  dist[a][b]=c
  dist[b][a]=c

dist = floyd_warshall(dist)

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

dist = floyd_warshall(dist)
dist[dist==INF]=0



Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

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

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

for i in range(N):
  dist[i][i]=0
  
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  dist[a][b]=c
  dist[b][a]=c

dist = floyd_warshall(dist)

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

dist = floyd_warshall(dist)
dist[dist==INF]=0



Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

for a in ans:
  print(-1 if a==INF else a)

Solution (Python):
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
ds = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c
for i in range(N):
    ds[i][i] = 0

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

ls = [[INF]*N for i in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if ds[i][j] <= L:
            ls[i][j] = ls[j][i] = 1
for i in range(N):
    ls[i][i] = 0

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

ans = []
for s,t in ST:
    ans.append(-1 if ls[s-1][t-1]==INF else ls[s-1][t-1] - 1)
print(*ans, sep='\n')

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    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

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


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

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

input = sys.stdin.readline


def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


N, M, L = map(int, input().split())
d = [[math.inf] * N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
warshall_floyd(d)
for i in range(N):
    for j in range(N):
        d[i][j] = 1 if d[i][j] <= L else math.inf
for i in range(N):
    d[i][i] = 0
warshall_floyd(d)


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

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, M, L = map(int, input().split())
dist = [[INF] * N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if c > L:
        continue
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c
Q = int(input())

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):
        fuel[i][j] = 1 if dist[i][j] <= L else INF
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 i in range(Q):
    s,t = map(int, input().split())
    if fuel[s - 1][t - 1] != INF:
        print(fuel[s - 1][t - 1] - 1)
    else:
        print(-1)

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, M, L = map(int, input().split())
dist = [[INF] * N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if c > L:
        continue
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c
Q = int(input())

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                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):
        fuel[i][j] = 1 if dist[i][j] <= L else INF
for k in range(N):
    for i in range(N):
        for j in range(N):
            if fuel[i][j] > fuel[i][k] + fuel[k][j]:
                fuel[i][j] = fuel[i][k] + fuel[k][j]
for i in range(Q):
    s,t = map(int, input().split())
    if fuel[s - 1][t - 1] != INF:
        print(fuel[s - 1][t - 1] - 1)
    else:
        print(-1)

Solution (Python):
import math

N, M, L = list(map(int, input().split()))
graph = [[math.inf]*N for _ in range(N)]

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

Q = int(input())
query = [(0, 0) for _ in range(Q)]

for i in range(Q):
    query[i] = tuple(map(int, input().split()))


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

fuel_cost = [[math.inf]*N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if graph[i][j] <= L:
            fuel_cost[i][j] = 1


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

for i in range(Q):
    if fuel_cost[query[i][0] - 1][query[i][1] - 1] == math.inf:
        print(-1)
    else:
        print(fuel_cost[query[i][0] - 1][query[i][1] - 1] - 1)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
全点対探索 & Nが小さいのでワーシャルフロイド．クエリも多めだし
合計距離から補給の回数をうまく計算するのは難しい，
残燃料を持つのも厳しい．
距離バージョンではなくて補給回数バージョンで新しいグラフとか作りたい

新しいグラフは距離がL以下の全点に対してならコスト1の辺を結ぶ．
最初からLあるのでコスト-1

"""
def main():
    
    def warshall_floyd(d):
        
        N=len(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
    
    mod=10**9+7
    N,M,L=MI()
    inf = 10**12
    d=[[inf]*N for _ in range(N)]
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c
        
    d=warshall_floyd(d)
    
    nd=[[inf]*N for _ in range(N)] 
    
    for i in range(N):
        for j in range(N):
            if d[i][j]<=L:
                nd[i][j]=1
    
    nd =warshall_floyd(nd)
    
    Q=I()
    for _ in range(Q):
        s,t=MI()
        s-=1
        t-=1
        ans=nd[s][t]
        if ans >= inf:
            ans=0
        print(ans-1)
        
    
    
    
main()

Solution (Python):
def warshall_floyd(n, edges):
    d = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for vf, vt, w in edges:
        d[vf][vt] = w
    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())
edges = []
for _ in range(m):
    a, b, w = map(int, input().split())
    if w <= l:
        edges.append((a-1, b-1, w))
        edges.append((b-1, a-1, w))
wf = warshall_floyd(n, edges)

edges.clear()
for i in range(n):
    for j in range(i + 1, n):
        if wf[i][j] <= l:
            edges.append((i, j, 1))
            edges.append((j, i, 1))
wf = warshall_floyd(n, edges)

q = int(input())
ans = [0] * q
for i in range(q):
    s, t = map(lambda x:int(x) - 1, input().split())
    ans[i] = -1 if wf[s][t] == float('inf') else wf[s][t] - 1
for x in ans:
    print(x)

Solution (Python):

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def resolve():
    INF = 10 ** 18
    N, M, L = map(int, input().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = G[b][a] = c

    G = csr_matrix(G)
    dist = floyd_warshall(G, directed=False)

    G2 = np.full((N, N), np.inf)  
    np.fill_diagonal(G2, 0)  
    G2[dist <= L] = 1

    dist2 = floyd_warshall(G2, directed=False)

    Q = int(input())
    for _ in range(Q):
        a, b = map(lambda x: int(x) - 1, input().split())
        if dist2[a][b] == np.inf:
            print(-1)
        else:
            print(int(dist2[a][b]) - 1)


if __name__ == "__main__":
    resolve()

Solution (Python):

def resolve():
    INF = 10 ** 18
    N, M, L = map(int, input().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = G[b][a] = c

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

    Cost = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if G[i][j] <= L:
                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][j], Cost[i][k] + Cost[k][j])

    Q = int(input())
    for _ in range(Q):
        a, b = map(lambda x: int(x) - 1, input().split())
        if Cost[a][b] == INF:
            print(-1)
        else:
            print(Cost[a][b] - 1)


if __name__ == "__main__":
    resolve()

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


def warshall_floyd(d,n):
    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[j][k])

    return d

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

d = [[INF for j in range(N)] for i in range(N)]
for i in range(M):
    a, b, c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

dd = [[INF for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if d[i][j] <= L:
            dd[i][j] = 1
            dd[j][i] = 1

dd = warshall_floyd(dd, N)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, l = map(int, input().split())
    cost = [[f_inf] * n for _ 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][j], cost[i][k] + cost[k][j])

    res = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if cost[i][j] <= l:
                res[i][j] = 1

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

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


if __name__ == '__main__':
    resolve()

Solution (Python):
n,m,l = map(int,input().split())
g = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    a-=1
    b-=1
    g[a][b] = c
    g[b][a] = c
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])
h = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j]<=l:
            h[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            h[i][j] = min(h[i][j],h[i][k] + h[k][j])
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    s -=1
    t-=1
    if h[s][t] ==float('inf'):
        print(-1)
    else:
        print(h[s][t]-1)

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
INF = 1 << 60


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())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c


dist = floyd_warshall(csr_matrix(dist))


dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF


dist2 = floyd_warshall(dist2, directed=False)
dist2 = dist2.astype(int)


dist2[dist2 == INF] = 0

q = int(input())


ans = []
for _ in range(q):
    s, t = map(int, input().split())
    ans.append(dist2[s - 1, t - 1] - 1)

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

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
INF = 1 << 60

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())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c


dist = floyd_warshall(csr_matrix(dist))

dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF
dist2 = floyd_warshall(dist2, directed=False)
dist2[dist2 == INF] = 0
dist2 = dist2.astype(int)

q = int(input())

ans = []
for _ in range(q):
    s, t = map(int, input().split())
    ans.append(dist2[s - 1, t - 1] - 1)

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

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, input().split())
INF = 1 << 60

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())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c


dist = floyd_warshall(csr_matrix(dist))

dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF
dist2 = floyd_warshall(dist2, directed=False)
dist2[dist2 == INF] = 0
dist2 = dist2.astype(int)

q = int(input())

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

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,l = inpl()
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a,b,c = inpl()
    d[a-1][b-1] = c
    d[b-1][a-1] = c
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])
e = [[INF]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            e[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            e[i][j] = min(e[i][j], e[i][k]+e[k][j])
q = inp()
for _ in range(q):
    a,b = inpl()
    ans = e[a-1][b-1]
    print(-1 if ans == INF else ans-1)

Solution (Python):
n, m, l = map(int, input().split())

INF = 1 << 30
g = [[INF] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

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

h = [[INF] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j] <= l:
            h[i][j] = 1

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

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

Solution (Python):


import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M,L = MI()

inf = 10**12
cost = [[inf]*(N+1) for _ in range(N+1)]  



for i in range(M):
    a,b,c = MI()
    cost[a][b] = c
    cost[b][a] = c

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

ans = [[inf]*(N+1) for _ in range(N+1)]  



for i in range(N+1):
    for j in range(N+1):
        if cost[i][j] <= L:
            ans[i][j] = 1

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

Q = I()
for i in range(Q):
    s,t = MI()
    if ans[s][t] == inf:
        print(-1)
        continue
    print(ans[s][t]-1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, L = mapint()
dist = [[10**18]*N for _ in range(N)]
for _ in range(M):
    a, b, c = mapint()
    dist[a-1][b-1] = c
    dist[b-1][a-1] = 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])

oil = [[10**18]*N for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        if dist[i][j]<=L:
            oil[i][j] = 1
            oil[j][i] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = mapint()
    if oil[s-1][t-1]>=10**17:
        print(-1)
    else:
        print(oil[s-1][t-1]-1)