#include using namespace std; #define int long long #define all(v) (v).begin(), (v).end() #define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__) #define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++) #define rep(i, n) reps(i, 0, n) template void chmin(T1 &a, T2 b){if(a>b)a=b;} template void chmax(T1 &a, T2 b){if(a; using Ti = tuple; using vint = vector; const int inf = 1LL << 55; const int mod = 1e9 + 7; struct edge { int to, cost; edge(){} edge(int to, int cost):to(to), cost(cost){} }; using Graph = vector>; signed main() { cin.tie(0); ios_base::sync_with_stdio(0); cout << fixed << setprecision(12); int N, M, K, S, T; cin >> N >> M >> K >> S >> T; --S, --T; map mp; vector buil(N); int sz = 0; mp[S] = sz++; buil[0].push_back(S); mp[(N-1)*K+T] = sz++; buil[N-1].push_back(T); vint a(M), b(M), c(M); rep(i, M) { cin >> a[i] >> b[i] >> c[i]; --a[i], --b[i], --c[i]; if(!mp.count(a[i]*K+b[i])) { mp[a[i]*K+b[i]] = sz++; buil[a[i]].push_back(b[i]); } if(!mp.count((a[i]+1)*K+c[i])) { mp[(a[i]+1)*K+c[i]] = sz++; buil[a[i]+1].push_back(c[i]); } } Graph graph(sz); rep(i, N) { sort(all(buil[i])); rep(j, buil[i].size()-1) { int s = mp[i*K+buil[i][j]]; int t = mp[i*K+buil[i][j+1]]; int cost = buil[i][j+1]-buil[i][j]; graph[s].emplace_back(t, cost); graph[t].emplace_back(s, cost); } } rep(i, M) { int s = mp[a[i]*K+b[i]]; int t = mp[(a[i]+1)*K+c[i]]; graph[s].emplace_back(t, 0); } vint mincost(sz, inf); priority_queue, greater> que; mincost[mp[S]] = 0; que.emplace(0, mp[S]); while(!que.empty()) { Pi p = que.top(); que.pop(); int v = p.second; if(mincost[v] < p.first) continue; if(v == mp[(N-1)*K+T]) { cout << mincost[v] << endl; return 0; } for(edge& e : graph[v]) { if(mincost[e.to] > mincost[v]+e.cost) { mincost[e.to] = mincost[v]+e.cost; que.emplace(mincost[e.to], e.to); } } } cout << -1 << endl; return 0; }