#include "train.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)
#include <vector>
using PP = pair<ll,ll>;
const ll INF = 1LL<<60;
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
std::vector<int> R) {
vector<pair<ll,ll>> P;
P.push_back({0,0});
rep(i,M){
P.push_back({X[i],A[i]});
P.push_back({Y[i],B[i]});
}
sort(all(P));
P.erase(unique(all(P)),P.end());
ll K=P.size();
vector<vector<pair<ll,ll>>> G(K);
rep(i,K){
if(i<K-1){
if(P[i].fi==P[i+1].fi){
G[i].push_back({i+1,0});
}
}
}
rep(i,M){
ll a=lower_bound(all(P),pair<ll,ll>(X[i],A[i]))-P.begin();
ll b=lower_bound(all(P),pair<ll,ll>(Y[i],B[i]))-P.begin();
G[a].push_back({b,C[i]});
}
vector<ll> dis(K,INF);
priority_queue<PP,vector<PP>,greater<PP>> pq;
dis[0]=0;
pq.emplace(dis[0],0);
while(!pq.empty()){
PP p=pq.top();
pq.pop();
ll v=p.se;
if(p.fi>dis[v]) continue;
for(auto e:G[v]){
if(dis[e.fi]>dis[v]+e.se){
dis[e.fi]=dis[v]+e.se;
pq.emplace(dis[e.fi],e.fi);
}
}
}
ll ans=INF;
rep(i,K){
if(P[i].fi==N-1){
ans=min(ans,dis[i]);
}
}
if(ans==INF) ans=-1;
return ans;
}
