#include "train.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (ll)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
const int MAXN = 1e3 + 5;
struct Train{
int planet;
int cost;
int start;
int end;
};
vector<Train> g[MAXN];
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) {
const ll INF = 3e18;
vector<vector<ll>> dp(N + 1, vector<ll> (MAXN + 1, INF));
vector<vector<bool>> vis(N + 1, vector<bool> (MAXN + 1, false));
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
for(int i = 0;i<M;++i){
g[X[i]].pb({Y[i], C[i], A[i], B[i]});
}
dp[0][0] = 0;
pq.push({0, {0, 0}});
while(!pq.empty()){
auto [nd, time] = pq.top().ss;
pq.pop();
if(vis[nd][time]) continue;
vis[nd][time] = true;
for(auto it:g[nd]){
if(time <= it.start){
ll cost = dp[nd][time] + it.cost;
for(int i = 0;i<W;++i){
if(time < L[i] and R[i] < it.start){
cost += T[nd];
}
}
if(cost < dp[it.planet][it.end]){
dp[it.planet][it.end] = cost;
pq.push({cost, {it.planet, it.end}});
}
}
}
}
ll ans = INF;
for(int time = 0;time<MAXN;++time){
ll cost = dp[N - 1][time];
for(int i = 0;i<W;++i) if(time < L[i]) cost += T[N - 1];
ans = min(ans, cost);
}
if(ans == INF) ans = -1;
return ans;
}
