#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)
const ll INF = 5e18;
struct Train {
int x, y, a, b, c;
bool operator<(const Train& other) const {
return b < other.b;
}
};
ll solve(int N, int M, int W, vint T, vint X, vint Y, vint A, vint B, vint C, vint L, vint R) {
if (W != 0) return -1;
vector<Train> trains(M); rep(i, M) trains[i] = {X[i], Y[i], A[i], B[i], C[i]};
sort(all(trains));
vll dp(N, INF); dp[0] = 0;
rep(i, M) {
dp[trains[i].y] = min(dp[trains[i].y], dp[trains[i].x] + trains[i].c);
}
ll res = dp[N-1];
if (res == INF) return -1;
return res;
}
