#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SEG{
private:
	int n;
	vector<int> node;
public:
	SEG(int N){
		n = 1;
		while(n < N) n *= 2;
		node.resize(2*n+1);
	}
	void add(int i, int x){
		for(i++;i<=n;i+=i&-i) node[i] += x;
	}
	int f_(int i){
		int ans = 0;
		for(;i>0;i-=i&-i) ans += node[i];
		return ans;
	}
	int f(int l, int r){
		return f_(r)-f_(l);
	}
};
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	srand((unsigned)time(NULL));
	int N,R,C;
	cin>>N>>R>>C;
	vector<vector<pair<int,int>>> G(6*N+1);
	int inf = 1e17;
	vector<int> dist(6*N+1,inf);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,0});
	dist[0] = 0;
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		G[i].push_back({i+N,a});
		G[i+3*N].push_back({i+4*N,a});
	}
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		G[i].push_back({i+2*N,a});
		G[i+3*N].push_back({i+5*N,a});
		G[i+N].push_back({i+2*N,a});
		G[i+4*N].push_back({i+5*N,a});
	}
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		G[i].push_back({i+3*N,a});
		G[i+N].push_back({i+4*N,a});
		G[i+2*N].push_back({i+5*N,a});
	}
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		for(int j=3;j<6;j++){
			G[i+N*j].push_back({6*N,a+C});
			G[6*N].push_back({i+N*j,a});
		}
	}
	for(int i=0;i<R;i++){
		int u,v,w,a,m;
		cin>>u>>v>>w>>a>>m;
		u--;
		v--;
		G[u].push_back({v,w});
		G[u+1*N].push_back({v+1*N,a});
		G[u+2*N].push_back({v+2*N,m});
		G[u+3*N].push_back({v+3*N,w});
		G[u+4*N].push_back({v+4*N,a});
		G[u+5*N].push_back({v+5*N,m});
		swap(u,v);
		G[u].push_back({v,w});
		G[u+1*N].push_back({v+1*N,a});
		G[u+2*N].push_back({v+2*N,m});
		G[u+3*N].push_back({v+3*N,w});
		G[u+4*N].push_back({v+4*N,a});
		G[u+5*N].push_back({v+5*N,m});
	}
	while(!pq.empty()){
		auto [w,u] = pq.top();
		pq.pop();
		if(dist[u] != w) continue;
		for(auto [v,x]:G[u])if(dist[v] > w+x){
			dist[v] = w+x;
			pq.push({dist[v],v});
		}
	}
	int ans = inf;
	for(int i=0;i<6;i++) ans = min(ans,dist[N-1+i*N]);
	cout<<ans<<endl;
}