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):
"""
気付き
１、float('inf')はちょい遅いみたい
２、input()よりもinput = sys.stdin.readlineの方が爆速らしい（知らんがな）
"""
import sys
inf = 10 ** 15
input = sys.stdin.readline

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

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



dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])



Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)

Solution (Python):
inf = 10 ** 15

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

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



dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])



Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)

Solution (Python):
import sys

input = sys.stdin.readline
N, M, L = list(map(int,input().split()))
P = [list(map(int,input().split())) for i in range(M)]
Q = int(input())
st = [list(map(int,input().split())) for i in range(Q)]

INF = 100100100100100

dp = [[INF]*N for i in range(N)]
for s,e,d in P:
	if d<=L:
		dp[s-1][e-1] = d
		dp[e-1][s-1] = d
for i in range(N):
	dp[i][i] = 0

for k in range(N):
	for y in range(N):
		for x in range(N):
			dp[y][x] = min(dp[y][x], dp[y][k]+dp[k][x])

dp2 = [[INF]*N for i in range(N)]
for y in range(N):
	for x in range(N):
		if dp[y][x]<=L:
			dp2[y][x] = 1

for k in range(N):
	for y in range(N):
		for x in range(N):
			dp2[y][x] = min(dp2[y][x], dp2[y][k]+dp2[k][x])

for s, t in st:
	count = dp2[s-1][t-1]
	if count==INF:
		print(-1)
	else:
		print(count-1)

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



N,M,L=map(int, raw_input().split())
RG=[[ 0 if i==j else float('inf') for i in range(N)] for j in range(N)]

for i in xrange(M):
    f,t,c = map(int, raw_input().split())
    if c <= L:
        RG[f-1][t-1] = c
        RG[t-1][f-1] = c

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(i, N):
            t = RG[i][k] + RG[k][j]
            if RG[i][j] > t:
                RG[i][j] = t
                RG[j][i] = t

FG=[[float('inf') for i in range(N)] for j in range(N)]
for i in xrange(N):
    for j in xrange(i, N):
        if RG[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(i, N):
            t = FG[i][k] + FG[k][j]
            if FG[i][j] > t:
                FG[i][j] = t
                FG[j][i] = t

Q=int(raw_input())
for i in xrange(Q):
    s, t = map(int, raw_input().split())
    v = FG[s-1][t-1]
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

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

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]






M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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






M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

Solution (Python):
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]






M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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






M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m, l = list(map(int, input().rstrip('\n').split()))
    wn = n
    wm = m
    inf = 10 ** 11
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    wn = n
    wm = m
    inf = 10 ** 11
    wl2 = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl2[i][i] = 0

    for i in range(wn):
        for j in range(wn):
            if wl[i][j] <= l:
                wl2[i][j] = 1

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl2[j][k] = min(wl2[j][k], wl2[j][i] + wl2[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        print(wl2[s-1][t-1] - 1 if wl2[s-1][t-1] != inf else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
n,m,l=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
q=int(input())
st=[list(map(int,input().split())) for _ in [0]*q]
inf=10**12
dist=[[inf]*n for _ in [0]*n]
for i in range(n):
    dist[i][i]=0
for a,b,c in abc:
    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])
inf=10**3
dist2=[[inf]*n for _ in [0]*n]
for i in range(n):
    for j in range(n):
        if dist[i][j]<=l:
            dist2[i][j]=1
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist2[i][j]=min(dist2[i][j],dist2[i][k]+dist2[k][j])
for i in range(n):
    for j in range(n):
        if dist2[i][j]==inf:
            dist2[i][j]=-1
        else:
            dist2[i][j]-=1
for s,t in st:
    print(dist2[s-1][t-1])

Solution (Python):
n,m,l = map(int,input().split())
inf = 10 ** 18
d1 = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
  d1[i][i] = 0
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  d1[a][b] = c
  d1[b][a] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d1[i][j] = min(d1[i][j], d1[i][k]+d1[k][j])
d2 = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if d1[i][j] == 0:
      d2[i][j] = 0
    elif d1[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])
q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  ans = d2[s][t]
  if ans >= inf:
    print(-1)
  else:
    print(ans-1)

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

n,m,l = map(int,input().split())
town = [list(map(int,input().split())) for _ in range(m)]
q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

inf = (l+1)*n
d = [[inf]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for a,b,c in town:
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    
def warshall_floyd(d,n):
    for k in range(n):
        for j in range(n):
            for i in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

warshall_floyd(d,n)

d2 = [None]*n
for i,row in enumerate(d):
    d2[i] = [1 if val<=l else inf for val in row]
    d2[i][i] = 0

warshall_floyd(d2,n)
 
for s,t in query:
    s -= 1
    t -= 1
    count = (d2[s][t]%inf)-1
    print(count)

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

N,M,L = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]
Q = int(input())
ST = [list(map(int,input().split())) for _ in [0]*Q]


INF = (L+1)*N
d = [[INF]*N for _ in [0]*N]
for i in range(N):
    d[i][i] = 0
for a,b,c in ABC:
    a-=1;b-=1
    d[a][b] = c
    d[b][a] = c

def Warshall_Floyd(d,N=None):
    if N==None : 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])

Warshall_Floyd(d,N)

d2 = [None]*N
for i,row in enumerate(d):
    d2[i] = [1 if e<=L else INF for e in row]
    d2[i][i] = 0

Warshall_Floyd(d2,N)

for s,t in ST:
    s-=1;t-=1
    ans = (d2[s][t]%INF)-1
    print(ans)

Solution (Python):
inf = float('inf')



def warshall_floyd(ad):
    n = len(ad)
    dist = [line[:] for line in ad]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int,input().split())
ad = [[inf] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int,input().split())
    if C > L:
        continue
    A -= 1
    B -= 1
    ad[A][B] = C
    ad[B][A] = C
Q = int(input())
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

ad = warshall_floyd(ad)
for s in range(N):
    for t in range(N):
        if ad[s][t] <= L:
            ad[s][t] = 1
        else:
            ad[s][t] = inf

ad = warshall_floyd(ad)
for s, t in query:
    ans = ad[s][t] - 1
    if ans == inf:
        ans = -1
    print(ans)

Solution (Python):
n,m,l=map(int,input().split())
g=[[999999999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    if c>l:
        continue
    g[a][b]=c
    g[b][a]=c

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]

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

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]

for i in range(int(input())):
    s,t=map(int,input().split())
    s-=1
    t-=1
    print(g[s][t]-1 if g[s][t]-1<99999999999 else -1)

Solution (Python):
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= map(int,input().split()) 

d=[[float("inf") for i 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
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)

d2=[[float("inf") for i in range(n)] for i in range(n)] 
for i in range(n):
    for j in range(n):
        if d[i-1][j-1]<=l:
            d2[i-1][j-1]=1
            d2[j-1][i-1]=1
warshall_floyd(d2)
q=int(input())
l=[list(map(int, input().split())) for i in range(q)]
for i in range(q):
    if d2[l[i][0]-1][l[i][1]-1]-1!=float('inf'):
        print(d2[l[i][0]-1][l[i][1]-1]-1)
    else:
        print(-1)

Solution (Python):
import sys


def naive_dijkstra(links, n, l):
    F30 = (1 << 30) - 1
    INF = 10 ** 18

    refuels = [[-1] * n for _ in range(n)]

    for s in range(n):
        rs = refuels[s]

        dists = [INF] * n
        dists[s] = 0
        remain_nodes = set(range(n))

        for _ in range(n):
            v = -1
            w = INF
            for u in remain_nodes:
                if dists[u] < w:
                    v = u
                    w = dists[u]
            if v == -1:
                break
            remain_nodes.remove(v)

            count = w >> 30
            used = w & F30
            rs[v] = count

            for u, c in links[v]:
                if l - used < c:
                    nw = ((count + 1) << 30) | c
                else:
                    nw = w + c
                if nw < dists[u]:
                    dists[u] = nw

    return refuels


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

dists = naive_dijkstra(links, n, l)
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(dists[s - 1][t - 1])

print('\n'.join(map(str, buf)))

Solution (Python):

from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int,input().split())
  
d = [[0 for i in range(N)] for j in range(N)] 
for i in range(M):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0

d = floyd_warshall(d, directed = False)
LN = [[0 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:
            LN[i][j] = 1
            LN[j][i] = 1

LN = floyd_warshall(LN, directed = False)    
s = []
t = []
Q = int(input())
for i in range(Q):
    s1, t1 = map(int,input().split())
    s.append(s1)
    t.append(t1)
for i in range(Q):
    if LN[s[i]-1][t[i]-1] == float("inf"):
        print(-1)
    else:
        print(int(LN[s[i]-1][t[i]-1]-1))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M, L = inpl()
road = [[] for _ in range(N)]
ABC = []
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
        ABC.append((A-1,B-1,C))

INF = 10**12
cur1 = [[INF]*N for _ in range(N)]
for a, b, c in ABC:
    cur1[a][b] = cur1[b][a] = c
for k in range(N):
    prev1 = cur1
    cur1 = [[INF]*N for _ in range(N)] 
    for j in range(N):
        for i in range(N):
            cur1[j][i] = min(prev1[j][i], prev1[k][i]+prev1[j][k])

cur2 = [[INF]*N for j in range(N)]
for j in range(N):
    for i in range(N):
        if cur1[j][i] <= L:
            cur2[j][i] = 1
for k in range(N):
    prev2 = cur2
    cur2 = [[INF]*N for _ in range(N)]
    for j in range(N):
        for i in range(N):
            cur2[j][i] = min(prev2[j][i], prev2[k][i]+prev2[j][k])

Q = int(input())
ST = [inpl() for _ in range(Q)]
for s,t in ST:
    if cur2[s-1][t-1] >= INF:
        print(-1)
    else:
        print(cur2[s-1][t-1]-1)

Solution (Python):
n, m, L = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
st = [list(map(int, input().split())) for _ in range(q)]

d = [[float('inf') for _ in range(n)] for _ in range(n)]
for a, b, c in abc:
    if c > L:
        continue
    d[a-1][b-1] = c
    d[b-1][a-1] = c

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            if i == k or d[i][k] > L:
                continue
            for j in range(n):
                if i == j:
                    continue
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

warshall_floyd(d)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif d[i][j] <= L:
            d[i][j] = 1
        else:
            d[i][j] = float('inf')

warshall_floyd(d)

for s, t in st:
    if d[s-1][t-1] == float('inf'):
        print(-1)
    else:
        print(d[s-1][t-1] - 1)

Solution (Python):
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import floyd_warshall
      
n,m,l = map(int,input().split())
edge = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c

edge = floyd_warshall(edge)
    
for i in range(n):
    for j in range(n):
        if edge[i][j]<=l:
            edge[i][j] = 1
        else:
            edge[i][j] = 0
                
edge = floyd_warshall(edge)

q = int(input())
for i in range(q):
    s,t = map(int,input().split())
    if edge[s-1][t-1] == float("inf"):
        print(-1)
    else:
        print(int(edge[s-1][t-1] - 1))

Solution (Python):
import sys

inp = sys.stdin

def input():
	return inp.readline().strip()

	
n, m, l = map(int, input().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

adjl = [[float('inf') for j in range(n)] for i in range(n)]
for i in range(n):
	adjl[i][i] = 0

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

adjl = warshall_floyd(adjl)

for i in range(n):
	for j in range(n):
		if i==j: adjl[i][j] = 0
		else: adjl[i][j] = 1 if adjl[i][j] <= l else float("inf")

adjl = warshall_floyd(adjl)

q = int(input())

for _ in range(q):
	a, b = map(int, input().split())
	ans = adjl[a-1][b-1]
	print(-1 if ans==float("inf") else ans-1)

Solution (Python):
from math import isinf


class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  
            for j in range(v_len):  
                for k in range(v_len):  
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


N, M, L = map(int, input().split())
adj = [[float('inf') for _ in range(N)] for _ in range(N)]
for A, B, C in [tuple(map(int, input().split())) for _ in range(M)]:
    adj[A - 1][B - 1] = C
    adj[B - 1][A - 1] = C

wf = WarshallFloyd(adj)

adj2 = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if wf.distance(i, j) <= L:
            adj2[i][j] = 1
wf2 = WarshallFloyd(adj2)

Q = int(input())
for s, t in [tuple(map(int, input().split())) for _ in range(Q)]:
    ans = wf2.distance(s - 1, t - 1) - 1
    if isinf(ans):
        print(-1)
    else:
        print(ans)

Solution (Python):
inf = 10 ** 10



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,w,L = map(int,input().split()) 

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

for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 
d = warshall_floyd(d)

D = [[inf for i in range(n)] for i in range(n)]

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

D = warshall_floyd(D)

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)

Solution (Python):


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, w, L = map(int, input().split())  
inf = 10**18
d = [[inf for i in range(n)] for _ in range(n)]

for i in range(w):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0  
d = warshall_floyd(d)

D = [[inf for i in range(n)] for i in range(n)]

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

D = warshall_floyd(D)

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)

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

N,M,L = map(int,input().split())
abc = [[int(i) for i in input().split()] for j in range(M)]
Q = int(input())
st = [[int(i) for i in input().split()] for j in range(Q)]
INF = 1<<30
Path = [[INF for i in range(N)] for j in range(N)]
AnsPath = [[INF for i in range(N)] for j in range(N)]

def PathInit():
    for i in range(N):
        Path[i][i] = 0

PathInit()
for i,j,k in abc:
    Path[i-1][j-1] = k
    
    Path[j-1][i-1] = k

Path = floyd_warshall(Path)

for i in range(N):
    for j in range(N):
        if Path[i][j] <= L:
            AnsPath[i][j] = 1
AnsPath = floyd_warshall(AnsPath)
for s,t in st:
    if AnsPath[s-1][t-1] == INF:
        print(-1)
    else:
        print(int(AnsPath[s-1][t-1]-1))

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

n,m,l=map(int,input().split())
ans=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    ans[a-1][b-1]=c
    ans[b-1][a-1]=c
q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])

ans=floyd_warshall(ans)

for i in range(n):
    for j in range(n):
        if ans[i][j]<=l:
            ans[i][j]=1
        else:
            ans[i][j]=0

ans=floyd_warshall(ans)

for i,j in st:
    if ans[i][j]==float("inf"):
        print(-1)
    else:
        print(int(ans[i][j])-1)

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

n,m,l=map(int,input().split())
ans=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    ans[a-1][b-1]=c
    ans[b-1][a-1]=c
q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])

ans=floyd_warshall(ans)

for i in range(n):
    for j in range(n):
        if ans[i][j]<=l:
            ans[i][j]=1
        else:
            ans[i][j]=0

ans=floyd_warshall(ans)

for i,j in st:
    if ans[i][j]==float("inf"):
        print(-1)
    else:
        print(int(ans[i][j])-1)

Solution (Python):
import sys
import numpy as np
import scipy.sparse as ss
f=ss.csgraph.floyd_warshall
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  d=f(f(ss.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]]
  d[d>n]=0
  print('\n'.join((d.astype(int)-1).astype(str).tolist()))
main()

Solution (Python):
import sys
import numpy as np
import scipy.sparse
f=scipy.sparse.csgraph.floyd_warshall
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  d=f(f(scipy.sparse.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]]
  d[d>n]=0
  print('\n'.join((d.astype(int)-1).astype(str).tolist()))
main()

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  d=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]]
  d[d>n]=0
  print('\n'.join((d.astype(int)-1).astype(str).tolist()))
main()

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Solution (Python):
import sys
from numpy import fromstring
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
def main():
  t=fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((floyd_warshall(floyd_warshall(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).astype(int)%n-1).astype(str).tolist()))
main()

Solution (Python):
import sys
from numpy import fromstring
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines


import numpy as np












from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall






def main():
    N,M,L=map(int,input().split())
    ABCQST=np.array(read().split(),np.int64)
    ABC=ABCQST[:3*M]
    A=ABC[::3]
    B=ABC[1::3]
    C=ABC[2::3]
    ST=ABCQST[3*M+1:]
    S=ST[::2]
    T=ST[1::2]

    graph1=csr_matrix((C,(A,B)),(N+1,N+1))
    graph1_dist=floyd_warshall(graph1,directed=False)

    graph2=np.full(((N+1),(N+1)),np.inf)
    np.fill_diagonal(graph2,0)
    graph2[graph1_dist<=L+0.5]=1

    graph2_dist=floyd_warshall(graph2,directed=False)
    graph2_dist[graph2_dist==np.inf]=0
    graph2_dist=(graph2_dist+0.5).astype(int)
    ans=graph2_dist[S,T]-1
    print("\n".join(ans.astype(str)))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromfile(open(0,'rb'),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromfile(open(0),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Solution (Python):
def main():
  import sys
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall as f
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(str).tolist()))
main()

Solution (Python):
import sys
from numpy import*
from scipy.sparse import*
f=csgraph.floyd_warshall
def main():
  t=fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((clip(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]],0,n).astype(int)%n-1).astype(str).tolist()))
main()