Buggy python submission (verdict: Time Limit Exceeded):
INF=10**15

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[INF*(L+1)+L] * self.V
        D[s]=0
        heapq.heappush(que,(0,s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)

            if cost>D[v]:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a=D[e.to]
                nokori=L-cost%(L+1)
                if nokori>=e.cost:
                    new=cost+e.cost
                else:
                    new=(cost//(L+1)+1)*(L+1)+e.cost
                if a>new:
                    D[e.to]=new
                    heapq.heappush(que,(D[e.to],e.to))

        return D

import sys

input=sys.stdin.readline

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=INF*(L+1)+L:
        print(ans[s-1][t-1]//(L+1))
    else:
        print(-1)


Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
INF=10**15

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[INF*(L+1)+L] * self.V
        D[s]=0
        heapq.heappush(que,(0,s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)

            if cost>D[v]:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a=D[e.to]
                nokori=L-cost%(L+1)
                if nokori>=e.cost:
                    new=cost+e.cost
                else:
                    new=(cost//(L+1)+1)*(L+1)+e.cost
                if a>new:
                    D[e.to]=new
                    heapq.heappush(que,(D[e.to],e.to))

        return D

import sys

input=sys.stdin.readline

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=INF*(L+1)+L:
        print(ans[s-1][t-1]//(L+1))
    else:
        print(-1)


Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[(10**15,L)] * self.V
        D[s]=(0,0)
        heapq.heappush(que,((0,0),s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)
            a,b=cost
            c,d=D[v]

            if a>c:
                continue
            elif a==c and b>d:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a,b=D[e.to]
                nokori=L-cost[1]
                if nokori>=e.cost:
                    c,d=cost[0],cost[1]+e.cost
                else:
                    c,d=cost[0]+1,e.cost
                if a>c or (a==c and b>d):
                    D[e.to]=(c,d)
                    heapq.heappush(que,(D[e.to],e.to))

        return D

import sys

input=sys.stdin.readline

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=(10**15,L):
        print(ans[s-1][t-1][0])
    else:
        print(-1)

Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[(10**15,L)] * self.V
        D[s]=(0,0)
        heapq.heappush(que,((0,0),s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)
            a,b=cost
            c,d=D[v]

            if a>c:
                continue
            elif a==c and b>d:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a,b=D[e.to]
                nokori=L-cost[1]
                if nokori>=e.cost:
                    c,d=cost[0],cost[1]+e.cost
                else:
                    c,d=cost[0]+1,e.cost
                if a>c or (a==c and b>d):
                    D[e.to]=(c,d)
                    heapq.heappush(que,(D[e.to],e.to))

        return D

import sys

input=sys.stdin.readline

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=(10**15,L):
        print(ans[s-1][t-1][0])
    else:
        print(-1)

Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
N,M,L=map(int,input().split())
d=[[10**20 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[b][a]=c

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

e=[[10**20 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if L>=d[i][j]:
            e[i][j]=1

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

Q=int(input())
ans=[]
for i in range(Q):
    s,t=map(int,input().split())
    if e[s][t]!=10**20:
        ans.append(e[s][t]-1)
    else:
        ans.append(-1)

for i in range(0,Q):
    print(ans[i])


Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
N,M,L=map(int,input().split())
d=[[10**20 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[b][a]=c

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

e=[[10**20 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if L>=d[i][j]:
            e[i][j]=1

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

Q=int(input())
ans=[]
for i in range(Q):
    s,t=map(int,input().split())
    if e[s][t]!=10**20:
        ans.append(e[s][t]-1)
    else:
        ans.append(-1)

for i in range(0,Q):
    print(ans[i])

Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self,s):

        import heapq
        que=[]
        D=[(10**15,L)] * self.V
        D[s]=(0,0)
        heapq.heappush(que,((0,0),s))

        while len(que)!=0:
            cost,v=heapq.heappop(que)
            a,b=cost
            c,d=D[v]

            if a>c:
                continue
            elif a==c and b>d:
                continue

            for i in range(len(self.G[v])):
                e=self.G[v][i]
                a,b=D[e.to]
                nokori=L-cost[1]
                if nokori>=e.cost:
                    c,d=cost[0],cost[1]+e.cost
                else:
                    c,d=cost[0]+1,e.cost
                if a>c or (a==c and b>d):
                    D[e.to]=(c,d)
                    heapq.heappush(que,(D[e.to],e.to))

        return D

N,M,L=map(int,input().split())
city=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    if L>=c:
        city.add(a-1,b-1,c)
        city.add(b-1,a-1,c)

ans=[city.shortest_path(i) for i in range(0,N)]

p=[]

Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if ans[s-1][t-1]!=(10**15,L):
        p.append(ans[s-1][t-1][0])
    else:
        p.append(-1)

for i in range(0,Q):
    print(p[i])

Fixed submission:
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())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

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

for i in range(Q):
    print(ans[i])