#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+6;
const ll inf = 1e18;
ll dis[N];
int par[N];
vector<pair<int, ll> > G[N];
map<pair<int,int>, int> mp;
inline ll dij(int s, int e, int n)
{
for(int i = 0; i < n; i++)
dis[i] = inf, par[i] = -1;
dis[s] = 0;
set<pair<ll, int> > st;
for(int i = 0; i < n; i ++)
st.insert({dis[i], i});
while(st.size())
{
int u = st.begin()->second;
st.erase(st.begin());
for(auto e : G[u]) {
int v = e.first, w = e.second;
if(dis[u] + w < dis[v]) {
st.erase({dis[v], v});
dis[v] = dis[u] + w;
par[v] = u;
st.insert({dis[v], v});
}
}
}
return (dis[e] == inf ? -1 : dis[e]);
}
#define F first
#define S second
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
vector<pair<int, pair<int,int> > > skywalks;
for(int i = 0; i < l.size(); i++)
skywalks.push_back({y[i], {l[i], r[i]}});
sort(skywalks.begin(), skywalks.end());
int n = x.size();
vector<int> high(x.size(), 0);
for(int i = 0; i < n; i ++)
mp[{x[i], 0}] = i;
set<int> st;
for(int i = 0; i < n; i ++)
st.insert(i);
for(int i = 0; i < skywalks.size(); i++)
{
int f = skywalks[i].S.F, s = skywalks[i].S.S, d = skywalks[i].F;
vector<int> nv, rem, xd;
auto it = st.lower_bound(f);
for(; it!= st.end() && *it <= s; it++){
int b = *it;
if(h[b] < d){
rem.push_back(b);
continue;
}
nv.push_back(mp[{x[b], d}]);
xd.push_back(x[b]);
if(high[b] == d) continue;
int yi = high[b];
int xi = x[b];
int v = mp[{xi, yi}];
mp[{xi, d}] = n;
nv.pop_back();
nv.push_back(n);
high[b] = d;
G[n].push_back({v, d - yi});
G[v].push_back({n, d - yi});
n++;
}
int v1 = nv[0];
for(int b = 1; b < nv.size(); b++) {
int v2 = nv[b];
G[v1].push_back({v2, xd[b] - xd[b-1]});
G[v2].push_back({v1, xd[b] - xd[b-1]});
v1 = v2;
}
for(int r : rem)
st.erase(r);
}
return dij(s, g, n);
}
/*
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
vector<int> x(n), h(n);
for (int i = 0; i < n; i++)
assert(2 == scanf("%d%d", &x[i], &h[i]));
vector<int> l(m), r(m), y(m);
for (int i = 0; i < m; i++)
assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
int s, g;
assert(2 == scanf("%d%d", &s, &g));
fclose(stdin);
long long result = min_distance(x, h, l, r, y, s, g);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
// */
