Buggy python submission (verdict: Time Limit Exceeded):
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [s]
        town[s][s] = s
        while q:
            z = heapq.heappop(q)
            u = z % MY
            if town[s][u] < z: continue
            n = z // MX
            w = (z % MX) // MY
            for v in range(N):
                c = road[u][v]
                if c == 0: continue
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw * MY + v
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,nz)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] < 0:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        town[s][s] = 0
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            if town[s][u] < z: continue
            n = z // MX
            w = z % MX
            for v in range(N):
                c = road[u][v]
                if c == 0: continue
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,(nz,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] < 0:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

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

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        town[s][s] = 0
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            if town[s][u] < z: continue
            n = z // MX
            w = z % MX
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,(nz,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] < 0:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    MX = 10**9
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

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

    town = [[[-1,0] for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            n = z // MX
            w = z % MX
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                if town[s][v][0] < 0 or town[s][v][0] > nn or \
                        town[s][v][0] == nn and town[s][v][1] > nw:
                    town[s][v][0] = nn
                    town[s][v][1] = nw
                    heapq.heappush(q,(nn*MX + nw,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        print(town[s-1][t-1][0])


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

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

    town = [[[-1,0] for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,-L,s)]
        heapq.heapify(q)
        while q:
            n,w,u = heapq.heappop(q)
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > 0:
                    nw = c - L
                    nn += 1

                if town[s][v][0] < 0 or town[s][v][0] > nn or \
                        town[s][v][0] == nn and town[s][v][1] > nw:
                    town[s][v][0] = nn
                    town[s][v][1] = nw
                    heapq.heappush(q,(nn,nw,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        print(town[s-1][t-1][0])


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        up = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        up = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

up = [False] + [True for _ in range(N)]
while up.count(True) > 0:
    for i in range(1,N+1):
        if up[i] == False : continue
        up[i] = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up[i] = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)
    
up = True
while up:
    up = False
    for i in range(1,N+1):
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True
                    
for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    for d,c in zip(rd[i], rc[i]):
        NP[i][d] = 0
        ZO[i][d] = L - c

up = True
while up:
    up = False
    for i in range(1,N+1):
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True
                    
for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    for j in range(len(rd[i])):
        d = rd[i][j]
        c = rc[i][j]
        NP[i][d] = 0
        ZO[i][d] = L - c

up = True
while up:
    up = False
    for i in range(1,N+1):
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for k in range(len(rd[j])):
                d = rd[j][k]
                if d == i: continue
                c = rc[j][k]
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq


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

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

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

    road = wf(road,N)


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

    gas = wf(gas,N)

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


if __name__ == '__main__':
    main()