#define _CRT_SECURE_NO_WARNINGS
/*
⣿⡟⡡⠾⠛⠻⢿⣿⣿⣿⡿⠃⣿⡿⣿⠿⠛⠉⠠⠴⢶⡜⣦⡀⡈⢿⣿
⡿⢀⣰⡏⣼⠋⠁⢲⡌⢤⣠⣾⣷⡄⢄⠠⡶⣾⡀⠀⣸⡷⢸⡷⢹⠈⣿
⡇⢘⢿⣇⢻⣤⣠⡼⢃⣤⣾⣿⣿⣿⢌⣷⣅⡘⠻⠿⢛⣡⣿⠀⣾⢠⣿
⣷⠸⣮⣿⣷⣨⣥⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢁⡼⠃⣼⣿
⡟⠛⠛⠛⣿⠛⠛⢻⡟⠛⠛⢿⡟⠛⠛⡿⢻⡿⠛⡛⢻⣿⠛⡟⠛⠛⢿
⡇⢸⣿⠀⣿⠀⠛⢻⡇⠸⠃⢸⡇⠛⢛⡇⠘⠃⢼⣷⡀⠃⣰⡇⠸⠇⢸
⡇⢸⣿⠀⣿⠀⠛⢻⡇⢰⣿⣿⡇⠛⠛⣇⢸⣧⠈⣟⠃⣠⣿⡇⢰⣾⣿
⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢋⣿⠙⣷⢸⣷⠀⣿⣿⣿
⣿⣿⣿⡇⢻⣿⣿⣿⡿⠿⢿⣿⣿⣿⠟⠋⣡⡈⠻⣇⢹⣿⣿⢠⣿⣿⣿
⣿⣿⣿⣿⠘⣿⣿⣿⣿⣯⣽⣉⣿⣟⣛⠷⠙⢿⣷⣌⠀⢿⡇⣼⣿⣿⣿
⣿⣿⣿⡿⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⡙⢿⢗⣀⣁⠈⢻⣿
*/
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//Donald Trump pleese save this code
//Babahnineeleven will win IOI 2040
//Babahnineeleven will win IOI 2041
//Babahnineeleven will win IOI 2042
//Babahnineeleven will win IOI 2043
//Babahnineeleven will win IOI 2044
//Babahnineeleven will win IOI 2045
//Babahnineeleven will win IOI 2046
//Babahnineeleven will win IOI 2047
//Babahnineeleven will win IOI 2048
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Kholod will win ICPC WF 2026
//Andrew Pavlyk is best coder in Khmelnytski
//MoonSlay will NOT get Into IOI
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#define endl '\n'
using namespace std;
FILE* stream;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef pair < ld, ld > pdd;
const long long DIM = 500007;
const ld eps = 1e-12;
const long long INF = 3e18;
const long long Bsize = 450;
const int mod = 1e9 + 7;
const long long NUMSZ = 500;
struct event {
int type;
int time, train;
};
bool cmp(event e1, event e2) {
if(e1.time != e2.time) return e1.time < e2.time;
return e1.type < e2.type;
}
ll 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) {
if (w == 0) {
vector < ll > d(n, INF);
d[0] = 0;
vector < ll > inTrain(m, INF);
vector < event > E;
for (int i = 0; i < m; i++) {
E.push_back({ 0, b[i], i });
E.push_back({ 1, a[i], i });
}
sort(E.begin(), E.end(), cmp);
for (auto q : E) {
if (q.type == 1 && d[x[q.train]] < INF) {
inTrain[q.train] = d[x[q.train]] + c[q.train];
}
if(q.type == 0) {
d[y[q.train]] = min(d[y[q.train]], inTrain[q.train]);
}
}
if (d[n - 1] == INF) return -1;
return d[n - 1];
}
else {
ll mxTime = 1e3 + 7;
vector < vector < int > > v(n);
for (int i = 0; i < m; i++) {
v[x[i]].push_back(i);
}
vector < vector < bool > > used(n, vector < bool >(mxTime, false));
vector < vector < ll > > dist(n, vector < ll >(mxTime, INF));
priority_queue < pair < ll, pll >, vector < pair < ll, pll > >, greater < pair < ll, pll > > > q;
dist[0][0] = 0;
q.push({ 0, {0, 0} });
while (!q.empty()) {
int val = q.top().second.first;
int time = q.top().second.second;
q.pop();
if (used[val][time]) continue;
used[val][time] = true;
for (auto e : v[val]) {
if (time <= a[e]) {
ll cost = dist[val][time] + c[e];
for (int j = 0; j < w; j++) if (time < L[j] && R[j] < a[e]) cost += (ll)t[val];
if (cost < dist[y[e]][b[e]]) {
dist[y[e]][b[e]] = cost;
q.push({ cost, {y[e], b[e]} });
}
}
}
}
ll res = INF;
for (int time = 0; time < mxTime; time++) {
ll cost = dist[n - 1][time];
for (int j = 0; j < w; j++) if (time < L[j]) cost += (ll)t[n - 1];
res = min(res, cost);
}
if (res == INF) return -1;
return res;
}
}
/*
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef _DEBUG
freopen_s(&stream, "input.txt", "r", stdin);
freopen_s(&stream, "output.txt", "w", stdout);
#endif
return 0;
}
*/
