#include "train.h"
#include <bits/stdc++.h>
#include <vector>
//#include "stub.cpp"
using namespace std;
typedef long long ll;
int n;
map<int , ll> dp[(int)2e5+1];
vector<vector<array<int , 4>>> adj(2e5+1);
ll brute(int i , int time){
if (i == n-1) return 0;
if (dp[i].count(time)) return dp[i][time];
ll ans = 1e18;
for (auto j : adj[i]){
if (time <= j[2]) ans = min(ans , brute(j[0] , j[3]) + j[1]);
}
return dp[i][time] = ans;
}
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){
n = N;
for (int i = 0 ; i < M ; i++){
adj[X[i]].push_back({Y[i] , C[i] , A[i] , B[i]});
}
ll ans = brute(0 , 0);
if (ans > 1e17) ans = -1;
return ans;
}