#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1010, M = 10010;
int c, n, m, s, u, v, x, y;
ll a[N], dis[N];
bool mp[N][N], vis[N], ck[N], ps[N];
struct edge{
	int to, add_x, add_y;
} dot;
vector <vector<edge>> g(N);
vector <vector<int>> rg(N);
queue <int> q, rq;

signed main() {
	freopen("recall.in", "r", stdin);
	freopen("recall.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> c >> n >> m >> s;
	for (int i = 1; i <= n; i++) cin >> a[i], dis[i] = -1;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v >> x >> y;
		if (!mp[u][v]) {
			g[u].push_back((edge){v, x, y});
			mp[u][v] = true;
		}
	}
	if (s + a[1] < 0) {
		cout << -1;
		return 0;
	}
	dis[1] = s + a[1];
	vis[1] = 1;
	q.push(1);
	ck[1] = true;
	for (int u = 1; u <= n; u++) {
		for (auto& e: g[u]) {
			rg[e.to].push_back(u);
		}
	}
	rq.push(n);
	ps[n] = true;
	while (!rq.empty()) {
		int v = rq.front();
		rq.pop();
		for (int u: rg[v]) {
			if (!ps[u]) {
				ps[u] = true;
				rq.push(u);
			}
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		ck[u] = false;
		if (!ps[u]) continue;
		for (auto& edge: g[u]) {
			int v = edge.to;
			int x = edge.add_x;
			int y = edge.add_y;
			if (x != 0 && y != 0 && !mp[x][y]) {
				dot = {y, 0, 0};
				g[x].push_back(dot);
				mp[x][y] = true;
				rg[y].push_back(x);
				if (ps[y] && !ps[x]) {
					ps[x] = true;
					rq.push(x);
				}
			}
			ll sum;
			if (!vis[v]) sum = dis[u] + a[v];
			else sum = dis[u];
			if (sum < 0) continue;
			if (sum > dis[v]) {
				dis[v] = sum;
				vis[v] = true;
				if (!ck[v]) {
					q.push(v);
					ck[v] = true;
				}
			}
		}
	}
	cout << (dis[n] == -1? -1: dis[n]) << endl;
	return 0;
}