直接分层图，然后注意每个点只需要连他下一层就行，连多了就T飞了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=1e3+10,M=1e5+10,MAXT=205;
int _=1,n,m,T,maxT,tot=0,ans=2e9,head[N],tp[N],dis[N][MAXT];
bool vis[N][MAXT];struct edge{int v,w,x,nxt;}a[M<<1];
struct node{
	int u,val,t;
	friend bool operator <(const node A,const node B){return A.val>B.val;}
};priority_queue<node> q;
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("B.in","r",stdin);
//	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}void add(int u,int v,int w,int x){
	a[++tot].v=v,a[tot].w=w,a[tot].x=x;
	a[tot].nxt=head[u];
	head[u]=tot;
}void dijkstra(int u,int t){
	memset(dis,0x3f,sizeof(dis));
	dis[u][t]=0,q.push(node{u,0,t});
	while(!q.empty()){
		int u=q.top().u,t=q.top().t;q.pop();
		if(vis[u][t]) continue;vis[u][t]=1;
		if(u==n){
			printf("%d\n",dis[n][t]);
			exit(0);
		}
		if(t+1<=maxT&&dis[u][t+1]>dis[u][t]+tp[u]){
			dis[u][t+1]=dis[u][t]+tp[u];
			q.push(node{u,dis[u][t+1],t+1});
		}for(int i=head[u];i;i=a[i].nxt){
			int v=a[i].v,x=a[i].x;
			if(t<x) continue;
			if(dis[v][t-x]>dis[u][t]+a[i].w){
				dis[v][t-x]=dis[u][t]+a[i].w;
				q.push(node{v,dis[v][t-x],t-x});
			}
		}
	}
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads(),T=reads(),maxT=reads();
		for(int i=1;i<=n;i++) tp[i]=reads();
		for(int i=1;i<=m;i++){
			int u,v,w,x;u=reads(),v=reads(),x=reads(),w=reads();
			add(u,v,w,x),add(v,u,w,x);
		}dijkstra(1,T);
		for(int i=0;i<=maxT;i++) ans=min(ans,dis[n][i]);
		printf("%d\n",ans);
	}return 0;
}