#include<bits/stdc++.h>
using namespace std; 
#define int long long
int shu[1005];
vector<int> v[1005];
vector<int> tu[1005][2];
int dian[1006];
int dian2[1006][1006];
priority_queue<pair<int,int>,vector<pair<int,int>> ,greater<pair<int,int>>>q;
int dis[200005];
int n,m;
bool pan[2000005];
void dsl(){
	dis[1]=0;
	q.push({0,1});
	//pan[s]=1;
	while(!q.empty()){
		int len=q.top().first;
		int dian=q.top().second;
		q.pop();
        if(pan[dian]==1)continue;
		pan[dian]=1;
		for(int i = 0;i<tu[dian][0].size();i++){
			if(pan[tu[dian][0][i]]==0 && dis[tu[dian][0][i]]>len+tu[dian][1][i] && len+tu[dian][1][i]<=0){
				dis[tu[dian][0][i]]=len+tu[dian][1][i];
				q.push({dis[tu[dian][0][i]],tu[dian][0][i]});
			}
		}
	}
}
signed main(){
	freopen("recall.in","r",stdin);
	freopen("recall.out","w",stdout);
    int c,si;
    cin>>c>>n>>m>>si;
    if(c==2){
        set<int> s;
        int ans=0;
        for(int i = 1;i<=n;i++)cin>>shu[i];
        for(int i = 1;i<=m;i++){
            int u,vi,x,y;
            cin>>u>>vi>>x>>y;
            v[u].push_back(vi);
            v[x].push_back(y);
            int l=s.size();
            s.insert(u);
            if(l!=s.size()){
                ans+=shu[u];
            }
            l=s.size();
            s.insert(vi);
            if(l!=s.size()){
                ans+=shu[vi];
            }
            l=s.size();
            s.insert(x);
            if(l!=s.size()){
                ans+=shu[x];
            }
            l=s.size();
            s.insert(y);
            if(l!=s.size()){
                ans+=shu[y];
            }
            
        }
        
        queue<int> q;
        q.push(1);
        dian[1]=1;
        int pan=0;
        while(!q.empty()){
            if(q.front()==n){
                pan=1;
                break;
            }
            for(int i = 0;i<v[q.front()].size();i++){
                if(dian[v[q.front()][i]]==0){
                    q.push(v[q.front()][i]);
                    dian[v[q.front()][i]]=1;
                }
            }
            q.pop();
            
        }
        if(pan==1)cout<<ans+si;
        else cout<<-1;
    }
    else if(c==3){
        int minn=0;
        for(int i = 1;i<=n;i++)cin>>shu[i];
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++)dian2[i][j]=INT_MAX;
        }
        
        for(int i = 1;i<=m;i++){
            int u,vi,x,y;
            cin>>u>>vi>>x>>y;
            dian2[u][vi]=shu[vi];
            if(dian2[u][vi]<0){
                dian2[u][vi]=abs(dian2[u][vi]);
            }
            else dian2[u][vi]=-dian2[u][vi];
            minn=min(minn,dian2[u][vi]);
        }
        for(int i = 1;i<=n;i++)dis[i]=INT_MAX;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(dian2[i][j]!=INT_MAX && i!=j){
                    
                    tu[i][0].push_back(j);
                    tu[i][1].push_back(dian2[i][j]);
                }
            }
        }
        dsl();
        if(shu[1]>=0 && dis[n]!=INT_MAX)cout<<abs(dis[n])+si+shu[1]<<endl;
        else cout<<-1;
        
        
        
    }
    else cout<<-1;
	return 0;
}