// 計算量がちょっと怖い #include #include #include #include #include using namespace std; typedef long long ll; int main(){ int n, m, k, s, t; cin >> n >> m >> k >> s >> t; set> sp; sp.insert({1, s}); sp.insert({n, t}); vector a(m), b(m), c(m); for(int i = 0; i < m; i++){ cin >> a[i] >> b[i] >> c[i]; sp.insert({a[i], b[i]}); sp.insert({a[i]+1, c[i]}); } map, int> p2id; int siz = 0; for(auto p : sp) p2id[p] = siz++; vector> vp[siz]; auto bef = sp.begin(); int id = 1; for(auto it = ++sp.begin(); it != sp.end(); it++){ if(it->first == bef->first){ int diff = it->second-bef->second; vp[id].push_back({id-1, diff}); vp[id-1].push_back({id, diff}); } bef = it; id++; } for(int i = 0; i < m; i++){ int ida = p2id[{a[i], b[i]}]; int idb = p2id[{a[i]+1, c[i]}]; vp[ida].push_back({idb, 0}); vp[idb].push_back({ida, 0}); } int from = p2id[{1, s}]; int to = p2id[{n, t}]; vector dp(siz, 1ll<<60); priority_queue> pq; dp[from] = 0; pq.push({-0, from}); while(!pq.empty()){ auto p = pq.top(); pq.pop(); ll cost = -p.first; int now = p.second; if(dp[now] != cost) continue; for(pair edge : vp[now]){ ll ncost = cost + edge.second; if(dp[edge.first] > ncost){ dp[edge.first] = ncost; pq.push({-ncost, edge.first}); } } } cout << (dp[to] == 1ll<<60 ? -1 : dp[to]) << endl; return 0; }