#include <bits/stdc++.h>
using namespace std;
struct Edge {int y, a, b; long long c;};
struct State {long long t, cost; int v, mask; bool operator<(const State&o)const{return cost>o.cost;}};
long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y,
vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {
vector<vector<Edge>> g(N);
for (int i=0;i<M;i++) g[X[i]].push_back({Y[i],A[i],B[i],C[i]});
long long INF = 4e18;
unordered_map<long long,long long> dist; // encode (v<<10)|mask
auto key=[&](int v,int m){return ((long long)v<<10)|m;};
priority_queue<State> pq;
pq.push({0,0,0,0});
dist[key(0,0)]=0;
while(!pq.empty()){
auto [t,c,v,mask]=pq.top(); pq.pop();
if(dist[key(v,mask)]<c) continue;
if(v==N-1 && mask==(1<<W)-1) return c;
// take meals on planet v if within L/R
for(int i=0;i<W;i++)
if(!(mask>>i&1) && L[i]<=t && t<=R[i]){
int nmask=mask|(1<<i);
long long nc=c+T[v];
if(dist[key(v,nmask)]>nc){
dist[key(v,nmask)]=nc;
pq.push({t,nc,v,nmask});
}
}
// board train
for(auto&e:g[v]) if(e.a>=t){
int nmask=mask;
for(int i=0;i<W;i++)
if(!(mask>>i&1)&&!(R[i]<e.a||L[i]>e.b))
nmask|=1<<i;
long long nc=c+e.c;
if(!dist.count(key(e.y,nmask))||dist[key(e.y,nmask)]>nc){
dist[key(e.y,nmask)]=nc;
pq.push({e.b,nc,e.y,nmask});
}
}
}
return -1;
}
