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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める"""
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    q = deque([start])
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # d = 補給回数 * 10 ** 15 + 使用燃料
    while q:
        v = q.popleft()
        d = dist[v]
        for nxt_v, cost in graph[v]:
            div_d, mod_d = divmod(d + cost, 10 ** 15)
            if mod_d > l:
                new_d = (div_d + 1) * 10 ** 15 + cost
            else:
                new_d = d + cost
            if new_d < dist[nxt_v]:
                dist[nxt_v] = new_d
                q.append(nxt_v)
    return dist


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

graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
ans = [[0] * n for i in range(n)]

for i in range(n):
    tmp = dijkstra(i, graph)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    q = [start]
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # d = 補給回数 * 10 ** 15 + 使用燃料
    while q:
        v = q.pop()
        d = dist[v]
        for nxt_v, cost in graph[v]:
            div_d, mod_d = divmod(d + cost, 10 ** 15)
            if mod_d > l:
                new_d = (div_d + 1) * 10 ** 15 + cost
            else:
                new_d = d + cost
            if new_d < dist[nxt_v]:
                dist[nxt_v] = new_d
                q.append(nxt_v)
    return dist


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

graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
ans = [[0] * n for i in range(n)]

for i in range(n):
    tmp = dijkstra(i, graph)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # d = 補給回数 * 10 ** 15 + 使用燃料
    q = [(0, start)] # q = [(d, 現在地)]
    while q:
        d, v = q.pop()
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            div_d, mod_d = divmod(d + cost, 10 ** 15)
            if mod_d > l:
                new_d = (div_d + 1) * 10 ** 15 + cost
            else:
                new_d = d + cost
            if new_d < dist[nxt_v]:
                dist[nxt_v] = new_d
                q.append((dist[nxt_v], nxt_v))
    return dist


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

graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
ans = [[0] * n for i in range(n)]

for i in range(n):
    tmp = dijkstra(i, graph)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def dfs(start):
        d = [inf]*n
        d[start] = 0
        f = [-1]*n
        f[start] = l
        dq = deque([start])
        while dq:
            v = dq.pop()
            nl = f[v]
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if d[v] < d[nv] or (d[v]==d[nv]and f[nv] < nl - c):
                        f[nv] = nl - c
                        d[nv] = d[v]
                        dq.append(nv)
                else:
                    if d[v]+1 < d[nv] or (d[v]+1==d[nv] and f[nv] < l-c):
                        f[nv] = l - c
                        d[nv] = d[v] + 1
                        dq.append(nv)
        return d

    res = []
    for i in range(n):
        res.append(dfs(i))

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

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def bfs(start):
        d = [inf]*n
        d[start] = 0
        f = [-1]*n
        f[start] = l
        dq = deque([[start, l, 0]])
        while dq:
            v, nl, dist = dq.popleft()
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if dist < d[nv] or (dist==d[nv]and f[nv] < nl - c):
                        f[nv] = nl - c
                        d[nv] = dist
                        dq.append((nv, nl - c, dist))
                else:
                    if dist + 1 < d[nv] or (dist+1==d[nv] and f[nv] < l-c):
                        f[nv] = l - c
                        d[nv] = dist + 1
                        dq.append((nv, l - c, dist + 1))
        return d

    res = []
    for i in range(n):
        res.append(bfs(i))

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

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # d = 補給回数 * 10 ** 15 + 使用燃料
    q = [(0, start)] # q = [(d, 現在地)]
    while q:
        d, v = heapq.heappop(q)
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            div_d, mod_d = divmod(d + cost, 10 ** 15)
            if mod_d > l:
                new_d = (div_d + 1) * 10 ** 15 + cost
            else:
                new_d = d + cost
            if new_d < dist[nxt_v]:
                dist[nxt_v] = new_d
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist


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

graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
ans = [[0] * n for i in range(n)]

for i in range(n):
    tmp = dijkstra(i, graph)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # d = 補給回数 * 10 ** 15 + 使用燃料
    q = [(0, start)] # q = [(d, 現在地)]
    while q:
        d, v = heapq.heappop(q)
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            div_d, mod_d = divmod(d + cost, 10 ** 15)
            if mod_d > l:
                new_d = (div_d + 1) * 10 ** 15 + cost
            else:
                new_d = d + cost
            if new_d < dist[nxt_v]:
                dist[nxt_v] = new_d
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist


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

graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
ans = [[0] * n for i in range(n)]

for i in range(n):
    tmp = dijkstra(i, graph)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # d = 補給回数 * 10 ** 15 + 使用燃料
    q = [(0, start)] # q = [(d, 現在地)]
    while q:
        d, v = heapq.heappop(q)
        #if dist[v] < d:
        #    continue
        for nxt_v, cost in graph[v]:
            div_d, mod_d = divmod(d + cost, 10 ** 15)
            if mod_d > l:
                new_d = (div_d + 1) * 10 ** 15 + cost
            else:
                new_d = d + cost
            if new_d < dist[nxt_v]:
                dist[nxt_v] = new_d
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist


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

graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
ans = [[0] * n for i in range(n)]

for i in range(n):
    tmp = dijkstra(i, graph)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([(0, start)]) # cost, 位置
    while q:
        _, pos = heapq.heappop(q)
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    heapq.heappush(q, (times,next_pos))
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        heapq.heappush(q, (times,next_pos))
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    heapq.heappush(q, (times,next_pos))
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        heapq.heappush(q, (times,next_pos))
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)


Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = sorted(graph[i], reverse = True)

def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    prev = -1
    q = deque([(start, prev)])
    while q:
        pos, prev = q.popleft()
        for next_pos, cost in graph[pos]:
            if prev == next_pos:
                continue
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append((next_pos, pos))
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append((next_pos, pos))
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append((next_pos, pos))
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append((next_pos, pos))
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    prev = -1
    q = deque([(start, prev)])
    while q:
        pos, prev = q.popleft()
        for next_pos, cost in graph[pos]:
            if prev == next_pos:
                continue
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append((next_pos, pos))
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append((next_pos, pos))
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append((next_pos, pos))
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append((next_pos, pos))
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.pop()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

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


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

    
def dfs(start):
    INF = float("inf")
    visited = [[INF, 0] for i in range(n)] # 回数, 残り燃料
    visited[start] = [0, 0]
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited[pos][1]
            times = visited[pos][0]
            next_times = visited[next_pos][0]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited[next_pos] = [times, tmp]
                elif next_times == times:
                    if visited[next_pos][1] > tmp:
                        q.append(next_pos)
                        visited[next_pos] = [times, tmp]
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited[next_pos] = [times + 1, tmp]
                elif next_times == times + 1:
                    if visited[next_pos][1] > tmp:
                        q.append(next_pos)
                        visited[next_pos] = [times + 1, tmp]
                else:
                    continue
    res = [0] * n
    for i in range(n):
        res[i] = visited[i][0]
    return res

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

def dfs(start):
    INF = float("inf")
    visited = [[INF, 0] for i in range(n)] # 回数, 残り燃料
    visited[start] = [0, 0]
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited[pos][1]
            if tmp <= l:
                if visited[next_pos][0] > visited[pos][0]:
                    q.append(next_pos)
                    visited[next_pos] = [visited[pos][0], tmp]
                elif visited[next_pos][0] == visited[pos][0]:
                    if visited[next_pos][1] > tmp:
                        q.append(next_pos)
                        visited[next_pos] = [visited[pos][0], tmp]
                else:
                    continue
            else:
                tmp = cost
                if visited[next_pos][0] > visited[pos][0] + 1:
                    q.append(next_pos)
                    visited[next_pos] = [visited[pos][0] + 1, tmp]
                elif visited[next_pos][0] == visited[pos][0] + 1:
                    if visited[next_pos][1] > tmp:
                        q.append(next_pos)
                        visited[next_pos] = [visited[pos][0] + 1, tmp]
                else:
                    continue
    visited =list(zip(*visited))
    return visited[0]

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

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

Fixed submission:
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)