注意到 $n\le 1000$，$T\le 200$，按照当前体力把图分成 $mxt$ 层，进行分层图最短路即可。

有几个要注意的地方：

• 一个点自己连边时，只需要连到他下一层。

• 当前点如果到了终点，直接输出。此时一定是最小的。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
int n,m,nwt,mxt,t[1005];
struct node {
	int v,w,c;
};
vector<node>G[1005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int dis[2000005];
bool vis[2000005];
void dijkstra(int s) {
	memset(dis,0x3f,sizeof dis),dis[s]=0,q.push({0,s});
	while(!q.empty()) {
		int tmp=q.top().second,j=tmp/n,u=tmp%n;
		if(u==n-1) {
			cout<<dis[tmp];
			exit(0);
		}
		q.pop();
		if(vis[tmp])continue;
		vis[tmp]=1;
		if(j+1<=mxt&&dis[(j+1)*n+u]>dis[j*n+u]+t[u]) {
			dis[(j+1)*n+u]=dis[j*n+u]+t[u];
			q.push({dis[(j+1)*n+u],(j+1)*n+u});
		}
		for(auto p:G[u]) {
			int v=p.v,w=p.w,c=p.c;
			if(j<w) continue;
			if(dis[(j-w)*n+v]>dis[j*n+u]+c) {
				dis[(j-w)*n+v]=dis[j*n+u]+c;
				q.push({dis[(j-w)*n+v],(j-w)*n+v});
			}
		}
	}
}
signed main() {
//	freopen("travel.in","r",stdin);
	R(n),R(m),R(nwt),R(mxt);
	for(int i=0; i<n; ++i) R(t[i]);
	while(m--) {
		int R(u),R(v),R(w),R(c);
		G[u-1].push_back({v-1,w,c});
		G[v-1].push_back({u-1,w,c});
	}
	dijkstra(nwt*n);
	return 0;
}