Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix

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

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

Rd = floyd_warshall(RG, directed=False)

FG=lil_matrix((N,N))
FG[Rd <= L] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix

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

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

Rd = floyd_warshall(RG, directed=False)

FG=lil_matrix((N,N))
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[(i,j)] = 1
            FG[(j,i)] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix

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

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

Rd = floyd_warshall(RG, directed=False)

FG=lil_matrix((N,N))
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[(i,j)] = 1
            FG[(j,i)] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix
import numpy

N,M,L=map(int, raw_input().split())
RG=lil_matrix((N,N))

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

Rd = floyd_warshall(RG, directed=False)

FG=lil_matrix((N,N))
for i in xrange(N):
    for j in xrange(i+1, N):
        if Rd[i][j] <= L:
            FG[(i,j)] = 1
            FG[(j,i)] = 1

Fd = floyd_warshall(FG, directed=False)

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



Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix
import numpy

N,M,L=map(int, raw_input().split())
RG=lil_matrix((N,N))

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

Rd = floyd_warshall(RG.tocsr())

FG=lil_matrix((N,N))
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[(i,j)] = 1
            FG[(j,i)] = 1

Fd = floyd_warshall(FG.tocsr())

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


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix
import numpy

N,M,L=map(int, raw_input().split())
RG=lil_matrix((N,N))

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

Rd = floyd_warshall(RG.tocsr())

vf = numpy.vectorize(lambda x: 1.0 if x <= L else float('inf'))

Fd = floyd_warshall(vf(Rd), directed=False)

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


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix,lil_matrix

N,M,L=map(int, raw_input().split())
RG=lil_matrix((N,N))

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

Rd = floyd_warshall(RG.tocsr())

FG=lil_matrix((N,N))
d = csr_matrix(Rd).todok()
for k,v in d.items():
    if v <= L:
        FG[k] = 1

Fd = floyd_warshall(FG.tocsr(), directed=False)

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


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N,M,L=map(int, raw_input().split())
RG=csr_matrix((N,N))

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

Rd = floyd_warshall(RG)

FG=csr_matrix((N,N))
for i in range(N):
    for j in range(N):
        if Rd[i][j] <= L:
            FG[(i,j)] = 1

Fd = floyd_warshall(FG, directed=False)

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


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

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

for i in range(M):
    f,t,c = map(int, raw_input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

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


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

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

for i in range(M):
    f,t,c = map(int, input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

Q=int(input())
Queries = []
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v -1)))



Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

MAX=pow(10,9) * 300
N,M,L=map(int, input().split())
Roads = [[ 0 if i == j else MAX for j in range(N)] for i in range(N)]

for i in range(M):
    f,t,c = map(int, input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

Q=int(input())
Queries = []
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v -1)))



Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import bisect

N,M,L=map(int, raw_input().split())
Roads = [] # from, to, cost
for i in range(M):
    Roads.append(map(int, raw_input().split()))
Q=int(raw_input())
Queries = [] # from, to
for i in range(Q):
    Queries.append(map(int, raw_input().split()))

def dijkstra(s, t):

    candidates = [[s,0,0]] # node, charge, used
    candidates_val = [0]

    while candidates:
        cn, cc, cu = candidates.pop(0)
        candidates_val.pop(0)
        if cn == t:
            return cc
        for fi, ti, ci in Roads:
            if fi == cn:
                node = ti
            elif ti == cn:
                node = fi
            else:
                continue

            if ci > L:
                continue
            elif cu + ci > L:
                charge = cc + 1
                used = ci
            else:
                charge = cc
                used = ci + cu

            cost = charge * L + used
            idx = bisect.bisect_left(candidates_val, cost)
            candidates_val.insert(idx, cost)
            candidates.insert(idx, [node, charge, used])
    return -1

for s,t in Queries:
    print dijkstra(s,t)


Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

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

N,M,L=map(int, raw_input().split())
Roads = [] # from, to, cost
for i in range(M):
    Roads.append(map(int, raw_input().split()))
Q=int(raw_input())
Queries = [] # from, to
for i in range(Q):
    Queries.append(map(int, raw_input().split()))

def dijkstra(s, t):

    candidates = [[s,0,0]] # node, charge, used
    confirmed = []

    while candidates:
        c = candidates.pop(0)
        confirmed.append(c)
        if c[0] == t:
            return c
        for i in Roads:
            if i[0] == c[0]:
                node = i[1]
            elif i[1] == c[0]:
                node = i[0]
            else:
                continue

            if i[2] > L:
                continue
            elif i[2] + c[2] > L:
                charge = c[1] + 1
                used = i[2]
            else:
                charge = c[1]
                used = c[2] + i[2]

            candidates.append([node, charge, used])
        candidates.sort(key=lambda x: x[1]*L+x[2])
    return None

for s,t in Queries:
    ret = dijkstra(s,t)
    if ret:
        print str(ret[1])
    else:
        print str(-1)

Fixed submission:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

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

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))