#include using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) int N,M,K,S,T; vector A,B,C; map dp[202020]; int main(){ cin >> N >> M >> K >> S >> T; A.resize(M); B.resize(M); C.resize(M); vector>> vec(N); rep(i,0,M - 1){ cin >> C[i] >> A[i] >> B[i]; C[i]--; vec[C[i]].push_back({B[i],A[i]}); } vec[N - 1].push_back({-1,T}); rep(i,0,N - 2){ sort(vec[i].begin(),vec[i].end()); } for(auto p : vec[0]){ dp[0][p.second] = abs(S - p.second); } rep(c,1,N - 1){ auto & before = vec[c - 1]; auto & next = vec[c]; vector up_min; vector bot_min; for(auto p : before){ i64 a = p.second; i64 b = p.first; if(up_min.empty()){ up_min.push_back(dp[c - 1][a] - b); } else{ up_min.push_back(min(up_min.back(),dp[c - 1][a] - b)); } } reverse(before.begin(),before.end()); for(auto p : before){ i64 a = p.second; i64 b = p.first; if(bot_min.empty()){ bot_min.push_back(dp[c - 1][a] + b); } else{ bot_min.push_back(min(bot_min.back(),dp[c - 1][a] + b)); } } reverse(before.begin(),before.end()); int cnt = 0; if(before.empty()){ cout << -1 << endl; return 0; } for(auto p : next){ i64 s = p.second; while(cnt < before.size() && s > before[cnt].first){ cnt++; } i64 MIN; if(cnt == 0){ MIN = bot_min[bot_min.size() - cnt - 1] - s; } else if(cnt == bot_min.size()){ MIN = up_min[cnt - 1] + s; } else{ MIN = min(bot_min[bot_min.size() - cnt - 1] - s, up_min[cnt - 1] + s); } dp[c][s] = MIN; } } cout << dp[N - 1][T] << endl; }