# import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') from collections import * from functools import * from heapq import * from itertools import * import sys, math,random input = sys.stdin.buffer.readline sys.setrecursionlimit(2*10**5) def cle(a, D): """ Counts the number of elements in D that are less than or equal to a. Parameters: a (int): The value to compare against. D (list): A sorted list of integers. Returns: int: The count of elements in D that are less than or equal to a. """ y = len(D) - 1 x = 0 if D[x] > a: return 0 if D[y] <= a: return y + 1 while y - x > 1: mid = (y + x) // 2 if D[mid] <= a: x = mid else: y = mid return y class cs_2d: """ 2D cumulative sum class. """ def __init__(self, x): """ Initializes the 2D cumulative sum array. Parameters: x (list of list of int): A 2D list of integers. """ n = len(x) m = len(x[0]) self.n = n self.m = m tmp = [0] * ((n + 1) * (m + 1)) for i in range(n): for j in range(m): tmp[m * (i + 1) + j + 1] = ( tmp[m * (i + 1) + j] + tmp[m * i + j + 1] - tmp[m * i + j] + x[i][j] ) self.S = tmp def query(self, ix, jx, iy, jy): """ Queries the sum of the submatrix from (ix, iy) to (jx, jy). Parameters: ix (int): Starting row index. jx (int): Ending row index. iy (int): Starting column index. jy (int): Ending column index. Returns: int: The sum of the submatrix. """ return ( self.S[self.m * jx + jy] - self.S[self.m * jx + iy] - self.S[self.m * ix + jy] + self.S[self.m * ix + iy] ) class prime_factorize: """ Class for prime factorization and related operations. """ def __init__(self, M=10**6): """ Initializes the sieve for prime factorization. Parameters: M (int): The maximum number to factorize. """ self.sieve = [-1] * (M + 1) self.sieve[1] = 1 self.p = [False] * (M + 1) self.mu = [1] * (M + 1) for i in range(2, M + 1): if self.sieve[i] == -1: self.p[i] = True i2 = i**2 for j in range(i2, M + 1, i2): self.mu[j] = 0 for j in range(i, M + 1, i): self.sieve[j] = i self.mu[j] *= -1 def factors(self, x): """ Returns the prime factors of x. Parameters: x (int): The number to factorize. Returns: list: A list of prime factors of x. """ tmp = [] while self.sieve[x] != x: tmp.append(self.sieve[x]) x //= self.sieve[x] tmp.append(self.sieve[x]) return tmp def divisors(self, x): """ Returns all divisors of x. Parameters: x (int): The number to find divisors for. Returns: list: A sorted list of all divisors of x. """ if x==1: return [1] C = Counter(self.factors(x)) tmp = [] for p in product(*[[pow(k, i) for i in range(v + 1)] for k, v in C.items()]): res = 1 for pp in p: res *= pp tmp.append(res) tmp.sort() return tmp def is_prime(self, x): """ Checks if x is a prime number. Parameters: x (int): The number to check. Returns: bool: True if x is prime, False otherwise. """ return self.p[x] def mobius(self, x): """ Returns the Möbius function value of x. Parameters: x (int): The number to find the Möbius function value for. Returns: int: The Möbius function value of x. """ return self.mu[x] class combination: """ Class for computing combinations (nCr) modulo p. """ def __init__(self, N, p): """ Initializes the combination class. Parameters: N (int): The maximum value of n. p (int): The modulus. """ self.fact = [1, 1] # fact[n] = (n! mod p) self.factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p) self.inv = [0, 1] # factinv calculation self.p = p for i in range(2, N + 1): self.fact.append((self.fact[-1] * i) % p) self.inv.append((-self.inv[p % i] * (p // i)) % p) self.factinv.append((self.factinv[-1] * self.inv[-1]) % p) def cmb(self, n, r): """ Computes the combination (nCr) modulo p. Parameters: n (int): The total number of items. r (int): The number of items to choose. Returns: int: The value of nCr modulo p. """ if (r < 0) or (n < r): return 0 r = min(r, n - r) return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p def md(n): """ Returns all divisors of n. Parameters: n (int): The number to find divisors for. Returns: list: A sorted list of all divisors of n. """ lower_divisors, upper_divisors = [], [] i = 1 while i * i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n // i) i += 1 return lower_divisors + upper_divisors[::-1] class DSU: """ Disjoint Set Union (Union-Find) class. """ def __init__(self, n): """ Initializes the DSU. Parameters: n (int): The number of elements. """ self._n = n self.parent_or_size = [-1] * n self.member = [[i] for i in range(n)] self._max = [i for i in range(n)] self._min = [i for i in range(n)] def merge(self, a, b): """ Merges the sets containing a and b. Parameters: a (int): An element in the first set. b (int): An element in the second set. Returns: int: The leader of the merged set. """ assert 0 <= a < self._n assert 0 <= b < self._n x, y = self.leader(a), self.leader(b) if x == y: return x if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x self.parent_or_size[x] += self.parent_or_size[y] self._max[x] = max(self._max[x],self._max[y]) self._min[x] = min(self._min[x],self._min[y]) for tmp in self.member[y]: self.member[x].append(tmp) self.parent_or_size[y] = x return x def get_max(self,x): return self._max[self.leader(x)] def get_min(self,x): return self._min[self.leader(x)] def members(self, a): """ Returns the members of the set containing a. Parameters: a (int): An element in the set. Returns: list: A list of members in the set containing a. """ return self.member[self.leader(a)] def same(self, a, b): """ Checks if a and b are in the same set. Parameters: a (int): An element in the first set. b (int): An element in the second set. Returns: bool: True if a and b are in the same set, False otherwise. """ assert 0 <= a < self._n assert 0 <= b < self._n return self.leader(a) == self.leader(b) def leader(self, a): """ Finds the leader of the set containing a. Parameters: a (int): An element in the set. Returns: int: The leader of the set containing a. """ assert 0 <= a < self._n if self.parent_or_size[a] < 0: return a self.parent_or_size[a] = self.leader(self.parent_or_size[a]) return self.parent_or_size[a] def size(self, a): """ Returns the size of the set containing a. Parameters: a (int): An element in the set. Returns: int: The size of the set containing a. """ assert 0 <= a < self._n return -self.parent_or_size[self.leader(a)] def groups(self): """ Returns all sets as a list of lists. Returns: list: A list of lists, where each list contains the members of a set. """ leader_buf = [self.leader(i) for i in range(self._n)] result = [[] for _ in range(self._n)] for i in range(self._n): result[leader_buf[i]].append(i) return [r for r in result if r != []] class SegTree: """ Segment Tree class. """ def __init__(self, init_val, segfunc, ide_ele): """ Initializes the Segment Tree. Parameters: init_val (list): The initial values for the leaves of the tree. segfunc (function): The function to use for segment operations. ide_ele (any): The identity element for the segment function. """ n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.log = (n-1).bit_length() self.tree = [ide_ele] * 2 * self.num # Set the initial values to the leaves for i in range(n): self.tree[self.num + i] = init_val[i] # Build the tree for i in range(self.num - 1, 0, -1): self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): """ Updates the k-th value to x. Parameters: k (int): The index to update (0-indexed). x (any): The new value. """ k += self.num self.tree[k] = x while k > 1: tk = k >> 1 self.tree[tk] = self.segfunc(self.tree[tk << 1], self.tree[(tk << 1) + 1]) k >>= 1 def get(self, x): return self.tree[x + self.num] def query(self, l, r): """ Queries the segment function result for the range [l, r). Parameters: l (int): The start index (0-indexed). r (int): The end index (0-indexed). Returns: any: The result of the segment function for the range [l, r). """ res_l = self.ide_ele res_r = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res_l = self.segfunc(res_l, self.tree[l]) l += 1 if r & 1: res_r = self.segfunc(self.tree[r - 1], res_r) l >>= 1 r >>= 1 res = self.segfunc(res_l, res_r) return res class RSQandRAQ(): """区間加算、区間取得クエリをそれぞれO(logN)で答える add: 区間[l, r)にvalを加える query: 区間[l, r)の和を求める l, rは0-indexed """ def __init__(self, n, mod=None): self.n = n self.bit0 = [0] * (n + 1) self.bit1 = [0] * (n + 1) self.mod = mod def _add(self, bit, i, val): i = i + 1 while i <= self.n: if self.mod is None: bit[i] += val else: bit[i] = (bit[i]+val)%self.mod i += i & -i def _get(self, bit, i): s = 0 while i > 0: if self.mod is None: s += bit[i] else: s = (s + bit[i])%self.mod i-= i & -i return s def add(self, l, r, val): """区間[l, r)にvalを加える""" self._add(self.bit0, l, -val * l) self._add(self.bit0, r, val * r) self._add(self.bit1, l, val) self._add(self.bit1, r, -val) def query(self, l, r): """区間[l, r)の和を求める""" _res = (self._get(self.bit0, r) + r * self._get(self.bit1, r) - self._get(self.bit0, l) - l * self._get(self.bit1, l) ) if self.mod is None: return _res else: return _res%self.mod class Dinic: def __init__(self, n): self.n = n self.links = [[] for _ in range(n)] self.depth = None self.progress = None def add_link(self, _from, to, cap): self.links[_from].append([cap, to, len(self.links[to])]) self.links[to].append([0, _from, len(self.links[_from]) - 1]) def bfs(self, s): depth = [-1] * self.n depth[s] = 0 q = deque([s]) while q: v = q.popleft() for cap, to, rev in self.links[v]: if cap > 0 and depth[to] < 0: depth[to] = depth[v] + 1 q.append(to) self.depth = depth def dfs(self, v, t, flow): if v == t: return flow links_v = self.links[v] for i in range(self.progress[v], len(links_v)): self.progress[v] = i cap, to, rev = link = links_v[i] if cap == 0 or self.depth[v] >= self.depth[to]: continue d = self.dfs(to, t, min(flow, cap)) if d == 0: continue link[0] -= d self.links[to][rev][0] += d return d return 0 def max_flow(self, s, t): flow = 0 while True: self.bfs(s) if self.depth[t] < 0: return flow self.progress = [0] * self.n current_flow = self.dfs(s, t, float('inf')) while current_flow > 0: flow += current_flow current_flow = self.dfs(s, t, float('inf')) INF = (1<<60) def dijkstra(s,e): dist = defaultdict(lambda:INF) dist[s]=0 h = [] # heappush(h,s) # while h: # nw,v = divmod(heappop(h),N) # if dist[v]!=nw: # continue # for iv,ic in e[v]: # nc = ic + nw # if nc < dist[iv]: # dist[iv] = nc # heappush(h,nc*N + iv) # return dist heappush(h,(0,s)) while h: nw,v = heappop(h) if dist[v]!=nw: continue for iv,ic in e[v]: nc = ic + nw if nc < dist[iv]: dist[iv] = nc heappush(h,(nc,iv)) return dist N,M,K,S,T = map(int,input().split()) e = defaultdict(list) X = defaultdict(list) X[1].append(S) X[N].append(T) for _ in range(M): a,b,c = map(int,input().split()) X[a].append(b) X[a+1].append(c) e[K*a+b-1].append((K*(a+1)+c-1,0)) for a,x in X.items(): x = list(set(x)) x.sort() n = len(x) if n==1: continue for i in range(n-1): ci = x[i] cj = x[i+1] d = abs(ci-cj) xi = K*a + ci - 1 xj = K*a + cj - 1 e[xi].append((xj,d)) e[xj].append((xi,d)) dist = dijkstra(K+S-1,e) val = dist[K*N+T-1] if val==INF: print(-1) else: print(val)