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):
from scipy.sparse import*
f=csgraph.floyd_warshall
t=map(int,open('/dev/fd/0').read().split())
n,m,l=t[:3]
m=m*3+3
for i in f(f(csr_matrix((t[5:m:3],(t[3:m:3],t[4:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1:print i

Solution (Python):
from scipy.sparse import*
f=csgraph.johnson
t=map(int,open('/dev/fd/0').read().split())
n,m,l=t[:3]
m=m*3+3
for i in f(f(csr_matrix((t[5:m:3],(t[3:m:3],t[4:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1:print i

Solution (Python):
def froyd(n, d):
    for k in range(n):
        for s in range(n):
            ds = d[s]
            for t in range(n):
                ds[t] = min(ds[t], ds[k] + d[k][t])


def main():
    N, M, L = [int(x) for x in input().split()]
    INF = float("inf")
    A = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    for i in range(N):
        A[i] = [INF] * N
        A[i][i] = 0
        B[i] = [INF] * N
        B[i][i] = 0
    for i in range(M):
        a, b, c = [int(x) for x in input().split()]
        A[a - 1][b - 1] = c
        A[b - 1][a - 1] = c
    froyd(N, A)
    
    for s in range(N):
        for t in range(N):
            B[s][t] = 0 if s == t else 1 if A[s][t] <= L else INF
    
    froyd(N, B)
    

    Q = int(input())
    for _ in range(Q):
        s, t = [int(x) for x in input().split()]
        b = B[s - 1][t - 1] - 1
        print(-1 if b == INF else b)


main()

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def warshall_floyd(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 = LI()
graph = [[] for _ in range(n)]
d = [[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c = LI()
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for i in range(n):
    d[i][i] = 0

d = warshall_floyd(d)

d2 = [[inf]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            d2[i][j] = 1

d2 = warshall_floyd(d2) 
q = I()
for _ in range(q):
    s,t = LI()
    if d2[s-1][t-1] == inf:
        print(-1)
    else:
        print(d2[s-1][t-1]-1)

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


def main():
    N, M, L = map(int, input().split())
    graph = [[INF]*N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        graph[A-1][B-1] = C
        graph[B-1][A-1] = C
    for i in range(N):
        graph[i][i] = 0
    for k in range(N):
        for i in range(N):
            if graph[i][k] == INF:
                continue
            for j in range(N):
                if graph[k][j] == INF:
                    continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    newGraph = [[INF]*N for _ in range(N)]
    for i in range(N):
        newGraph[i][i] = 0
        for j in range(i+1, N):
            if graph[i][j] <= L:
                newGraph[i][j] = 1
                newGraph[j][i] = 1
    for k in range(N):
        for i in range(N):
            if newGraph[i][k] == INF:
                continue
            for j in range(N):
                if newGraph[k][j] == INF:
                    continue
                newGraph[i][j] = min(newGraph[i][j], newGraph[i][k] + newGraph[k][j])
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        if newGraph[s-1][t-1] == INF:
            print(-1)
        else:
            print(newGraph[s-1][t-1]-1)


if __name__ == '__main__': main()

Solution (Python):
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  f=floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join((f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1).astype(int).astype(str)))
main()

Solution (Python):
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  f=floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,floyd_warshall(floyd_warshall(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
import sys
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
import sys
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,clip(f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),(n+1,n+1)),0)<=l)[t[m+1::2],t[m+2::2]],0,n)%n-1))))
main()

Solution (Python):
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,clip(f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),(n+1,n+1)),0)<=l)[t[m+1::2],t[m+2::2]],0,n)%n-1))))
main()

Solution (Python):
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Solution (Python):
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  m*=3
  *_,=map(print,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1)
main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,L=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        if(c>L): continue
        a-=1; b-=1
        E[a].append((b,c))
        E[b].append((a,c))
    A=[0]*n
    
    for u in range(n):
        dist=[(INF,INF)]*n 
        dist[u]=(0,0)
        calculated=[False]*n
        for _ in range(n-1):
            v=min((dist[v],v) for v in range(n) if(not calculated[v]))[1]
            calculated[v]=True
            now=dist[v]
            for nv,w in E[v]:
                if(now[1]+w<=L):
                    next=(now[0],now[1]+w)
                else:
                    next=(now[0]+1,w)
                if(dist[nv]>next):
                    dist[nv]=next
        A[u]=dist
    
    Q=int(input())
    for _ in range(Q):
        s,t=map(int,input().split())
        s-=1; t-=1
        ans=A[s][t][0]
        print(ans if ans!=INF else -1)
resolve()

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

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

distance = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    distance[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    distance[a-1][b-1] = c
    distance[b-1][a-1] = c

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

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

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

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = distance[s-1][t-1]-1
    if ans is float('inf'):
        ans = -1
    print(ans)

Solution (Python):
N,M,L = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
    
Q = int(input())
qlist = [[int(q) for q in input().split()] for _ in range(Q)]

INF = 10**18
d = [[INF]*N for _ in range(N)]
for i in range(M):
    d[A[i]-1][B[i]-1] = C[i]
    d[B[i]-1][A[i]-1] = C[i]

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



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

d2 = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        elif d[i][j] <= L:
            d2[i][j] = 1
            
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][j], d2[i][k]+d2[k][j])
                
for i in range(Q):
    s = qlist[i][0]-1
    t = qlist[i][1]-1
    ans = d2[s][t]
    if ans >= INF:
        print(-1)
    else:
        print(ans-1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n,m,l = map(int,input().split())
    d = [[10**12]*n for _ in [0]*n]
    for i in range(m):
        a,b,c = map(int,input().split())
        if l >= c:
            d[a-1][b-1] = d[b-1][a-1] = c
    for i in range(n):
        d[i][i] = 0

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

    edge = [[10**12]*n for _ in [0]*n]
    for i in range(n):
        for j in range(n):
            if d[i][j] <= l:
                edge[i][j] = 1

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

    q = int(input())
    for _ in [0]*q:
        s,t = map(int,input().split())
        if edge[s-1][t-1] >= 10**12:
            print(-1)
        else:
            print(edge[s-1][t-1]-1)

if __name__ == '__main__':
    main()

Solution (Python):
from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
*_,=map(print,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1)

Solution (Python):
from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
print(*f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1,sep='\n')

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

n, m, l = map(int, input().split())
INF = float("inf")

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[k][j])
    return d

d = [[INF for i in range(n)] for j 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
d = warshall_floyd(d, n)

d2 = [[INF for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l: d2[i][j] = 1
    d2[i][i] = 0
d2 = warshall_floyd(d2, n)

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

Solution (Python):
S = raw_input()
S = S.split()
n,m,l = int(S[0]),int(S[1]),int(S[2])
MAX = int(1e15)
G = []
for i in xrange(n):
    temp=[]
    for j in xrange(n):
        temp.append(MAX)
    G.append(temp)
for i in xrange(n):
    G[i][i]=0

for i in xrange(m):
    S = raw_input()
    S = S.split()
    a,b,c = int(S[0]),int(S[1]),int(S[2])
    a-=1
    b-=1
    G[a][b]=c
    G[b][a]=c
for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            val = G[i][k]+G[k][j]
            G[i][j] = min(G[i][j],val)
dd = G
for i in xrange(n):
    for j in xrange(n):
        if(dd[i][j]<=l):
            G[i][j]=1
        else :
            G[i][j]=MAX
        if(i==j):
            G[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            val = G[i][k]+G[k][j]
            G[i][j] = min(G[i][j],val)

q = input()
while(q):
    q-=1
    S = raw_input()
    S =S.split()
    s,t = int(S[0]),int(S[1])
    s-=1
    t-=1
    p = G[s][t]
    if(p>=MAX):
        print -1
    else:
        print p-1

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        
        res[i][i] = 0
    
    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])
    return res

N, M, L = MAP()
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1
    b -= 1
    G[a][b] = c
    G[b][a] = c

res = warshall_floyd(N, G)

G2 = list2d(N, N, INF)
for i in range(N):
    for j in range(i, N):
        
        if res[i][j] <= L:
            G2[i][j] = 1
            G2[j][i] = 1


res2 = warshall_floyd(N, G2)

for i in range(INT()):
    a, b = MAP()
    a -= 1
    b -= 1
    ans = res2[a][b]
    if ans != INF:
        print(ans-1)
    else:
        print(-1)

Solution (Python):
from scipy.sparse import*;f=csgraph.johnson;n,m,l,*t=map(int,open(0).read().split());m*=3;d=f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l);d[d>n]=0;print(*d[t[m+1::2],t[m+2::2]]-1,sep='\n')

Solution (Python):
from scipy.sparse import*;f=csgraph.dijkstra;n,m,l,*t=map(int,open(0).read().split());d=f(f(csr_matrix((t[2:m*3:3],(t[:m*3:3],t[1:m*3:3])),(n+1,n+1)),0)<=l);d[d>n]=0;print(*d[t[m*3+1::2],t[m*3+2::2]]-1,sep='\n')

Solution (Python):
import sys
from numpy import*
from scipy.sparse import*
f=csgraph.floyd_warshall
n,m,l,*t=map(int,sys.stdin.buffer.read().split())
t=int32(t)
d=f(f(csr_matrix((t[2:m*3:3],(t[:m*3:3],t[1:m*3:3])),(n+1,n+1)),0)<=l)-1
d[d==inf]=-1
print('\n'.join(map(str,map(int,d[t[m*3+1::2],t[m*3+2::2]]))))

Solution (Python):
import sys
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  t=int32(t)
  d=f(f(csr_matrix((t[2:m*3:3],(t[:m*3:3],t[1:m*3:3])),(n+1,n+1)),0)<=l)-1
  d[d==inf]=-1
  print('\n'.join(map(str,map(int,d[t[m*3+1::2],t[m*3+2::2]]))))
main()

Solution (Python):
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])
    return d


INF = 10**9 + 1

if __name__ == "__main__":
    N, M, L = map(int, input().split())
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for i in range(M):
        tmp = list(map(int, input().split()))
        D[tmp[0]-1][tmp[1]-1] = tmp[2]
        D[tmp[1]-1][tmp[0]-1] = tmp[2]
    Q = int(input())
    st = list()
    for i in range(Q):
        st.append(list(map(int, input().split())))

    D = warshall_floyd(D)

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

    D = warshall_floyd(D)

    for i in range(Q):
        ans = D[st[i][0]-1][st[i][1]-1] - 1
        if ans == INF - 1:
            print(-1)
        else:
            print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')



input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

def wf(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


n,m,l=MI()
d=[[inf]*n for _ in range(n)]
for i in range(m):
    a,b,c=LI_()
    d[a][b]=c+1
    d[b][a]=c+1

d=wf(d)
g=[[inf]*n for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        if d[i][j]<=l:
            g[i][j]=1
            g[j][i]=1
g=wf(g)

q=I()
for _ in range(q):
    s,t=LI_()
    if g[s][t]==inf:
        ans=-1
    else:
        ans=g[s][t]-1
    print(ans)

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=floyd_warshall(floyd_warshall(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join([str(int(d[i]))for i in zip(*[iter(t[m*3+1:])]*2)]))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=floyd_warshall(floyd_warshall(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,[int(d[i])for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=floyd_warshall(floyd_warshall(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,[int(d[i])for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,[int(d[i])for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)
  d[d>n]=0
  d-=1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d==float('inf')]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype(int)
  print('\n'.join(map(str,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2))))))
main()

Solution (Python):
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2))))))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i2')
  print('\n'.join(map(str,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2)))))
main()

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

N, M, L, *I = map(int, open(0).read().split())
ABC, ST = I[:3 * M], I[3 * M + 1:]

E = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a - 1][b - 1] = E[b - 1][a - 1] = c

E = floyd_warshall(E)
E = [[(eij <= L) for j, eij in enumerate(ei)] for i, ei in enumerate(E)]
E = floyd_warshall(E)

INF = float("inf")

A = []
for s, t in zip(*[iter(ST)] * 2):
    a = E[s - 1][t - 1] - 1
    A.append("-1" if a == INF else str(int(a)))

print("\n".join(A))

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2))))))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
input=sys.stdin.buffer.readline
def main():
  n,m,l=map(int,input().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for _ in range(m):
    a,b,c=map(int,input().split())
    d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  a=[d[tuple(map(int,input().split()))]for _ in range(int(input()))]
  print('\n'.join(map(str,map(int,a))))
main()

Solution (Python):
import sys
import scipy.sparse.csgraph as s
f=s.floyd_warshall
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i2')
  print('\n'.join(map(str,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i2').astype('U')
  print('\n'.join(d[i]for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(str(int(d[i]))for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)
  d[d>n]=0
  print('\n'.join(map(str,map(int,[d[i]-1for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
inf = float('inf')
def dijkstra(s):
    d = [(inf, 1)] * N
    used = [False] * N
    d[s] = (0, -L)  
    for i in range(N):
        v = -1
        for i in range(N):
            if used[i]:
                continue
            if v==-1:
                v = i
            elif d[v]>d[i]:
                v = i
        if v == -1:
            break
        used[v] = True   
        m, r = d[v]
        r = -r
        for nv in range(N):
            c = cost[v][nv]
            if r>=c:
                d[nv] = min(d[nv],(m, -(r-c)))
            elif c<=L:
                d[nv] = min(d[nv], (m+1, -(L-c)))
    return d
N, M, L = map(int, input().split())
cost = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c
ans = []
for i in range(N):
    ans.append(dijkstra(i))
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    res = ans[a-1][b-1][0]
    print(res if res != inf else -1)

Solution (Python):
inf = 10**10
def dijkstra(s):
    d = [(inf, 1)] * N
    used = [False] * N
    d[s] = (0, -L)  
    for i in range(N):
        v = -1
        for i in range(N):
            if used[i]:
                continue
            if v==-1:
                v = i
            elif d[v]>d[i]:
                v = i
        if v == -1:
            break
        used[v] = True   
        m, r = d[v]
        r = -r
        for nv in range(N):
            c = cost[v][nv]
            if r>=c:
                d[nv] = min(d[nv],(m, -(r-c)))
            elif c<=L:
                d[nv] = min(d[nv], (m+1, -(L-c)))
    return d
N, M, L = map(int, input().split())
cost = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c
ans = []
for i in range(N):
    ans.append(dijkstra(i))
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    res = ans[a-1][b-1][0]
    print(res if res != inf else -1)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in'_'*(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()