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

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != (alt - 1) // l and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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


Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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

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

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if (r != (alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d
 
n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in abc:
  a,b,cost = i[0]-1, i[1]-1, i[2]
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
for i in st:
  s, t = i[0] - 1, i[1] - 1
  ans = ans_list[s][t]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)


Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if (r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d
 
n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in abc:
  a,b,cost = i[0]-1, i[1]-1, i[2]
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
for i in st:
  s, t = i[0] - 1, i[1] - 1
  ans = ans_list[s][t]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)


Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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

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

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            if ((dist_v - 1) // l) != ((alt - 1) // l) and dist_v != 0:
                alt = ((dist_v - 1) // l + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d
 
n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in abc:
  a,b,cost = i[0]-1, i[1]-1, i[2]
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
for i in st:
  s, t = i[0] - 1, i[1] - 1
  ans = ans_list[s][t]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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

Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            if (dist_v - 1) // l != (alt - 1) // l and dist_v != 0:
                alt = ((dist_v - 1) // l + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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


Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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

Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            if (dist_v - 1) // l != (alt - 1) // l and dist_v != 0:
                alt = ((dist_v - 1) // l + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in abc:
  a,b,cost = i[0]-1, i[1]-1, i[2]
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
for i in st:
  s, t = i[0] - 1, i[1] - 1
  ans = ans_list[s][t]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans_list[s][t] - 1) // l
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
  
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):

    def __init__(self, graph, start,l):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if dist_u != 0:
                  if (dist_u - 1) // l != (alt - 1) // l:
                    alt = ((dist_u - 1) // l + 1) * l + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        if self.dist[goal] == float("inf"):
          return -1
        return (self.dist[goal] - 1) // l


    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = Graph()
for i in abc:
  a,b,c = i[0], i[1], i[2]
  if c <= l:
    path.add_edge(a-1, b-1, c)
    path.add_edge(b-1, a-1, c)
for i in st:
  s,t = i[0]-1, i[1]-1
  s_path = Dijkstra(path, s, l)
  ans = s_path.shortest_distance(t)
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

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