#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'
const ll T = 1001;
ll solve(int n, int m, int w, vector<int> p, vector<int> x, vector<int> y, vector<int> a, vector<int> b, vector<int> c, vector<int> l, vector<int> r){
vector<tuple<ll,ll,ll,ll>> g[n];
for(ll i=0; i<m; i++){
g[x[i]].push_back({y[i], a[i], b[i], c[i]});
}
#define tup tuple<ll,ll,ll>
priority_queue<tup, vector<tup>, greater<tup>> pq;
vector<vector<ll>> dist(n, vector<ll>(T, inf));
pq.push({0, 0, 0});
dist[0][0] = 0;
while(!pq.empty()){
auto [d, v, t] = pq.top();
pq.pop();
if(dist[v][t] != d) continue;
for(auto [ch, aa, bb, ww] : g[v]){
if(t > aa) continue;
ll td = d;
for(ll i=0; i<w; i++){
if(l[i] > t and r[i] < aa) td += p[v];
}
if(td + ww < dist[ch][bb]){
dist[ch][bb] = td + ww;
pq.push({dist[ch][bb], ch, bb});
}
}
}
ll ans = inf;
for(ll t=0; t<T; t++){
ll d = dist[n-1][t];
for(ll i=0; i<w; i++){
if(l[i] > t) d += p[n-1];
}
ans = min(ans, d);
}
return ans == inf ? -1 : ans;
}
