//MRasol kheyri
//Iran -> Khorasan -> ferdows -> Baghestan
//15/2/1405
//vasate azmoonima...
#include<bits/stdc++.h>
#include "train.h"
using namespace std ;
typedef long long ll ;
#define el '\n'
const ll maxn = 1e6 + 100 ;
const ll oo = 1e17 + 100 ;
ll n , m , dis[maxn] ;
vector<pair<ll,pair<ll,ll>>> adj[maxn] ;
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) {
n = N , m = M ;
for(ll i = 0 ; i < m ; i++){
adj[X[i]].push_back({Y[i],{A[i],B[i]}}) ;
}
fill(dis,dis+n,oo) ;
set<pair<ll,ll>> s ;
s.insert({0,0}) ;
while(s.size()){
ll u = (*s.begin()).second , w = (*s.begin()).first ;
s.erase(s.begin()) ;
if(dis[u] != oo){continue;}
dis[u] = w ;
for(auto x : adj[u]){
ll v = x.first , A = x.second.first , B = x.second.second ;
if(A < dis[u] || dis[v] != oo){continue;}
s.insert({B,v}) ;
}
}
return dis[n-1] == oo ? -1 : dis[n-1] ;
}
