Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
from heapq import heappop, heappush
from collections import defaultdict

def dijkstra(start, goal, edges,
             start_distance=0,
             plus_func=lambda D,d: D+d):
    '''
    goal: int or list or set
    edges: list or dict
        edges[x] = (y, distance)
    '''
    q = [(start_distance, start)]
    done = set()
    if isinstance(goal, int):
        goal_set = {goal}
    else:
        goal_set = set(goal)
    ret = defaultdict(lambda: None)
    minimum = defaultdict(lambda: None)

    while q:
        D, x = heappop(q)
        if x in done:
            continue
        elif x in goal_set:
            ret[x] = D
            goal_set.remove(x)
            if len(goal_set) == 0:
                return ret
        done.add(x)
        for y, d in edges[x]:
            if not y in done:
                m = minimum[y]
                p = plus_func(D,d)
                if m is None or m > p:
                    heappush(q, (p, y))
                    minimum[y] = p
    return ret

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
ans = [[None]*N for _ in range(N)]

Q = int(input())
ST = []
goals = [set() for _ in range(N)]
for _ in range(Q):
    s, t = inpl()
    s -= 1
    t -= 1
    ST.append((s, t))
    goals[s].add(t)

def plus(D, d):
    refuel, oil = D
    if oil + d > L:
        return (refuel+1, d)
    else:
        return (refuel, oil+d)

for s in range(N):
    if goals[s]:
        result = dijkstra(s, goals[s], road, (0,0), plus)
        for t in goals[s]:
            d = result[t]
            if d is None:
                ans[s][t] = -1
            else:
                ans[s][t] = result[t][0]

for s, t in ST:
    print(ans[s][t])


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
ans = [[-1]*N for _ in range(N)]

Q = int(input())
ST = []
goals = [set() for _ in range(N)]
for _ in range(Q):
    s, t = inpl()
    s -= 1
    t -= 1
    ST.append((s, t))
    goals[s].add(t)

for s in range(N):
    if not goals[s]:
        continue
    q = [((0,0), s)]
    done = [False]*N
    goal_n = len(goals[s])
    goal_flag = [False]*N
    for g in goals[s]:
        goal_flag[g] = True
    while q:
        D, x = heappop(q)
        refuel, oil = D
        if done[x]:
            continue
        elif goal_flag[x]:
            ans[s][x] = refuel
            goal_n -= 1
            if goal_n == 0:
                break
        done[x] = True
        for y, d in road[x]:
            if done[y]:
                continue
            if oil + d > L:
                heappush(q, ((refuel+1, d), y))
            else:
                heappush(q, ((refuel, oil+d), y))

for s, t in ST:
    print(ans[s][t])


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
ans = [[-1]*N for _ in range(N)]

Q = int(input())
ST = []
goals = [set() for _ in range(N)]
for _ in range(Q):
    s, t = inpl()
    s -= 1
    t -= 1
    ST.append((s, t))
    goals[s].add(t)

for s in range(N):
    if not goals[s]:
        continue
    q = [((0,0), s)]
    done = set()
    goal_set = set(goals[s])
    while q:
        D, x = heappop(q)
        refuel, oil = D
        if x in done:
            continue
        elif x in goal_set:
            ans[s][x] = refuel
            goal_set.remove(x)
            if len(goal_set) == 0:
                break
        done.add(x)
        for y, d in road[x]:
            if y in done:
                continue
            if oil + d > L:
                heappush(q, ((refuel+1, d), y))
            else:
                heappush(q, ((refuel, oil+d), y))

for s, t in ST:
    print(ans[s][t])


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
from heapq import heappop, heappush
from collections import defaultdict

def dijkstra(start, goal, edges,
             start_distance=0,
             plus_func=lambda D,d: D+d):
    '''
    goal: int or list or set
    edges: list or dict
        edges[x] = (y, distance)
    '''
    q = [(start_distance, start)]
    done = set()
    if isinstance(goal, int):
        goal_set = {goal}
    else:
        goal_set = set(goal)
    ret = defaultdict(lambda: None)

    while q:
        D, x = heappop(q)
        if x in done:
            continue
        elif x in goal_set:
            ret[x] = D
            goal_set.remove(x)
            if len(goal_set) == 0:
                return ret
        done.add(x)
        for y, d in edges[x]:
            if not y in done:
                heappush(q, (plus_func(D,d), y))
    return ret

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
ans = [[None]*N for _ in range(N)]

Q = int(input())
ST = []
goals = [set() for _ in range(N)]
for _ in range(Q):
    s, t = inpl()
    s -= 1
    t -= 1
    ST.append((s, t))
    goals[s].add(t)

def plus(D, d):
    refuel, oil = D
    if oil + d > L:
        return (refuel+1, d)
    else:
        return (refuel, oil+d)

for s in range(N):
    if goals[s]:
        result = dijkstra(s, goals[s], road, (0,0), plus)
        for t in goals[s]:
            d = result[t]
            if d is None:
                ans[s][t] = -1
            else:
                ans[s][t] = result[t][0]

for s, t in ST:
    print(ans[s][t])


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [(-1,0)]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = (0,0)

Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
for start in starts:
    prev = {start}
    while prev:
        cur = set()
        for p in prev:
            for q, c in road[p]:
#                print(p,q)
                pn, pred = minimum[start][p]
                qn, qred = minimum[start][q]
                if pred + c > L:
                    qn2, qred2 = pn + 1, c
                else:
                    qn2, qred2 = pn, pred + c
                if qn < 0 or qn2 < qn or (qn2==qn and qred2 < qred):
                    minimum[start][q] = qn2, qred2
                    cur.add(q)
#                    print(start,q,qn2,qred2)
        prev = cur

#print(minimum)

for s,t in ST:
    print(minimum[s-1][t-1][0])

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [(-1,0)]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = (0,0)

Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
for start in starts:
    prev = {start}
    while prev:
        cur = set()
        for p in prev:
            for q, c in road[p]:
                pn, pred = minimum[start][p]
                qn, qred = minimum[start][q]
                if pred + c > L:
                    qn2, qred2 = pn + 1, c
                else:
                    qn2, qred2 = pn, pred + c
                if qn < 0 or qn2 < qn or (qn2==qn and qred2 < qred):
                    minimum[start][q] = qn2, qred2
                    cur.add(q)
        prev = cur

for s,t in ST:
    print(minimum[s-1][t-1][0])

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])