#include #include #include #include #include #include #include #include using namespace std; using int64 = long long; using P = pair; using State = pair; using Edge = tuple; // (次の棟, 渡り廊下のある階(自分), 渡り廊下のある階(相手)) const int maxn = 300000; const int64 inf = (1LL << 50); vector G[maxn]; map dist; int main() { int N, M, K, S, T; cin >> N >> M >> K >> S >> T; assert(1 <= N and N <= 200000); assert(0 <= M and M <= 200000); assert(1 <= K and K <= 2e9); assert(1 <= S and S <= K); assert(1 <= T and T <= K); for (int i = 0; i < M; i++) { int a, b; int64 c; cin >> a >> b >> c; assert(1 <= a and a <= N - 1); assert(1 <= b and b <= K); assert(1 <= c and c <= K); P p1 = {a, b}, p2 = {a + 1, c}; dist[p1] = dist[p2] = inf; G[a].emplace_back(a + 1, b, c); // G[a + 1].emplace_back(a, c, b); } dist[{N, T}] = inf; priority_queue, greater> Q; Q.push({0, {1, S}}); dist[{1, S}] = 0; int64 ans = inf; while (!Q.empty()) { auto q = Q.top(); Q.pop(); int64 d = q.first; int p = q.second.first; int h = q.second.second; if (dist[{p, h}] < d) continue; if (p == N) ans = min(ans, abs(h - T) + d); for (Edge& e : G[p]) { int next, cur_s, nxt_s; tie(next, cur_s, nxt_s) = e; if (dist[{next, nxt_s}] > abs(cur_s - h) + d) { dist[{next, nxt_s}] = abs(cur_s - h) + d; Q.push({dist[{next, nxt_s}], {next, nxt_s}}); } } } if (ans >= inf) cout << -1 << endl; else cout << ans << endl; return 0; }