#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxn=155;
int ans=1e18; 

struct node{
	int u;
	int d;
	int yellow;
	int xiansu;
	int duan;
	
	bool operator <(const node &cmp) const{
		return d>cmp.d;
	}
};

struct light{
	int g;
	int y;
	int r;
};
light a[maxn];

struct edge{
	int to;
	int bxian;
	int xian;
};
vector<edge> G[maxn];

int dist[maxn][maxn][maxn];//节点 限速几段 闯了几个黄灯 
int n,m,k,g;

int check(int t,int i){
	int sum=a[i].g+a[i].y+a[i].r;
	t%=sum;
	if (t<a[i].g) return 1;
	if (t>=a[i].g&&t<a[i].g+a[i].y) return 2;
	return 3;
}

int get(int t,int i){
	int sum=a[i].g+a[i].y+a[i].r;
//	if (t%sum==0) return t;
	
	int yushu=t%sum;
	return t+(sum-yushu);
} 

void solve(){
	priority_queue<node> q;
	while (!q.empty()) q.pop();
	
	for (int i=0;i<=105;i++){
		for (int j=0;j<=105;j++){
			for (int x=0;x<=105;x++) dist[i][j][x]=1e18;
		}
	}
	dist[1][0][0]=0;
	q.push((node){1,0,0,0,0});
	
	while (!q.empty()){
		node f=q.top(); q.pop();
		int u=f.u,xiansu=f.xiansu,d=f.d;
	//	printf("%lld %lld %lld %lld %lld\n",f.u,f.d,f.yellow,f.xiansu,f.duan);
		if (xiansu>k||f.yellow>g||d>dist[u][xiansu][f.yellow]) continue;
		
		if (u==n){
			if (f.duan-f.xiansu<=m-k&&f.yellow<=g) ans=min(ans,f.d);
			continue;
		}
		
		for (int i=0;i<(int)G[u].size();i++){
			int v=G[u][i].to;
			
			if (check(f.d,u)==1){
				if (dist[v][xiansu+1][f.yellow]>dist[u][xiansu][f.yellow]+G[u][i].xian){
		//			printf("a\n");
					dist[v][xiansu+1][f.yellow]=dist[u][xiansu][f.yellow]+G[u][i].xian;
					q.push((node){v,dist[v][xiansu+1][f.yellow],f.yellow,xiansu+1,f.duan+1});
				}
				
				if (dist[v][xiansu][f.yellow]>dist[u][xiansu][f.yellow]+G[u][i].bxian){
		//			printf("b\n"); 
					dist[v][xiansu][f.yellow]=dist[u][xiansu][f.yellow]+G[u][i].bxian;
					q.push((node){v,dist[v][xiansu][f.yellow],f.yellow,xiansu,f.duan+1});
				}
			}else if (check(f.d,u)==2){
				if (dist[v][xiansu+1][f.yellow+1]>dist[u][xiansu][f.yellow]+G[u][i].xian){
		//			printf("c\n");
					dist[v][xiansu+1][f.yellow+1]=dist[u][xiansu][f.yellow]+G[u][i].xian;
					q.push((node){v,dist[v][xiansu+1][f.yellow+1],f.yellow+1,xiansu+1,f.duan+1});
				}
				
				if (dist[v][xiansu][f.yellow+1]>dist[u][xiansu][f.yellow]+G[u][i].bxian){
		//			printf("d\n");
					dist[v][xiansu][f.yellow+1]=dist[u][xiansu][f.yellow]+G[u][i].bxian;
					q.push((node){v,dist[v][xiansu][f.yellow+1],f.yellow+1,xiansu,f.duan+1});
				}
				
				if (dist[v][xiansu+1][f.yellow]>get(f.d,u)+G[u][i].xian){
		//			printf("e\n");
					dist[v][xiansu+1][f.yellow]=get(f.d,u)+G[u][i].xian;
					q.push((node){v,dist[v][xiansu+1][f.yellow],f.yellow,xiansu+1,f.duan+1});
				}
				
				if (dist[v][xiansu][f.yellow]>get(f.d,u)+G[u][i].bxian){
			//		printf("f\n");
					dist[v][xiansu][f.yellow]=get(f.d,u)+G[u][i].bxian;
					q.push((node){v,dist[v][xiansu][f.yellow],f.yellow,xiansu,f.duan+1});
				}
			}else{
		//		printf("enter 3 %lld\n",get(f.d,u));
				if (dist[v][xiansu+1][f.yellow]>get(f.d,u)+G[u][i].xian){
		//			printf("g\n");
					dist[v][xiansu+1][f.yellow]=get(f.d,u)+G[u][i].xian;
					q.push((node){v,dist[v][xiansu+1][f.yellow],f.yellow,xiansu+1,f.duan+1});
				}
				
				if (dist[v][xiansu][f.yellow]>get(f.d,u)+G[u][i].bxian){
		//			printf("h\n"); 
					dist[v][xiansu][f.yellow]=get(f.d,u)+G[u][i].bxian;
					q.push((node){v,dist[v][xiansu][f.yellow],f.yellow,xiansu,f.duan+1});
				}
			}
		}
	}
}

signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&k,&g);
	for (int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].g,&a[i].y,&a[i].r);
	
	for (int i=1;i<=m;i++){
		int u,v,xian,bxian;
		scanf("%lld%lld%lld%lld",&u,&v,&bxian,&xian);
		G[u].push_back((edge){v,bxian,xian});
		G[v].push_back((edge){u,bxian,xian});
	}
	
	solve();
	printf("%lld\n",ans);
	return 0;
}

评测记录