#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,m,s,t,T;
int h[305],idx,e[N],ne[N],a[N],b[N],w[N];
int st[305],d[305];
void add(int u,int v,int aa,int bb,int ww){
	e[++idx]=v;
	a[idx]=aa;
	b[idx]=bb;
	w[idx]=ww;	
	
	ne[idx]=h[u];
	h[u]=idx;
}
struct PII{
	int pos,dis;
	friend bool operator< (PII x,PII y){
		return x.dis > y.dis;
	}
};
void dijkstra(){
	for(int i=0;i<=n;i++){
		d[i]=1e9+100,st[i]=0;
	}
	priority_queue<PII>q;
	while(q.size())q.pop();
	d[s]=0;
	q.push({s,0});
	while(q.size()){
		PII o=q.top();q.pop();
		int x=o.pos,y=o.dis;
		if(st[x])continue;
		st[x]=1;
		for(int i=h[x];i;i=ne[i]){
			int v=e[i];
			int dd=y%(a[i]+b[i]);
			if(dd>=a[i]){//路口关闭
				if(b[i]-(dd-a[i])+w[i]+y<d[v]){
					d[v]=b[i]-(dd-a[i])+w[i]+y;
					if(!st[v])q.push({v,d[v]});
				}
			}
			else{//路口开启
				if(a[i]-dd>=w[i]&&w[i]+y<d[v]){//剩余时间可以恰好通过
					d[v]=w[i]+y;
					if(!st[v])q.push({v,d[v]});
				}
				else if(a[i]-dd<w[i]&&a[i]+b[i]-dd+w[i]+y<d[v]){
					d[v]=a[i]+b[i]-dd+w[i]+y;
					if(!st[v])q.push({v,d[v]});
				}
			}
		}
	}
	
}
int main(){
	while(~scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF){
		for(int i=0;i<=n;i++)h[i]=0;
		idx=0;
		for(int i=0;i<=m;i++)e[i]=ne[i]=a[i]=b[i]=w[i]=0;
		
		int u,v,aa,bb,ww;
		for(int i=1;i<=m;i++){
			cin>>u>>v>>aa>>bb>>ww;
			if(ww>aa)continue;
			add(u,v,aa,bb,ww);
		}
		dijkstra();
		printf("Case %d: %d\n",++T,d[t]);
	}
}