#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
#define int long long
struct PII{
	int x,sum;
	friend bool operator<(PII A,PII B)
	{
		return A.sum>B.sum;
	}
};
int h[N],e[N],ne[N],w[N],a[N],b[N],idx=1,cnt=1,n,m,ss,tt,st[N],d[N];
void add(int u,int v,int A,int B,int T)
{
	e[idx]=v;
	w[idx]=T;
	a[idx]=A;
	b[idx]=B;
	ne[idx]=h[u];
	h[u]=idx++;
//	printf("idx=%lld u=%lld v=%lld h=%lld\n",idx,u,v,h[u]);
}
void djstla()
{
	for(int i=0;i<=n;i++){d[i]=1e9;st[i]=0;}
	priority_queue<PII>q;
	q.push({ss,0});
	d[ss]=0;
	while(q.size())
	{
		PII t=q.top();
		q.pop();
//		printf("t.x=%lld dis=%lld\n",t.x,t.sum);
		if(st[t.x])continue;
		st[t.x]=1;
		int num=t.x,dis=t.sum;
//		printf("h=%lld \n",h[num]);
		for(int i=h[num];i;i=ne[i])
		{
			int y=e[i];
	//		printf("i=%lld y=%lld \n",i,y);
			if(!st[y])
			{
				int xx=dis,aa=a[i],bb=b[i];
				int yy=w[i],res=1e9;
				if(xx%(aa+bb)<=aa)//开门
				{
					int tt=xx/(aa+bb)*(aa+bb)+aa;
					if((xx+yy)<=tt)//剩余时间可以通过
					{
						res=xx+yy;
					}
					else 
					{
						tt+=(aa+bb);
						if((xx+aa+bb-xx%(aa+bb)+yy)<=tt)
						{
							res=xx+aa+bb-xx%(aa+bb)+yy;
						}
					}
				}
				else//关门 
				{
					int tt=xx/(aa+bb)*(aa+bb)+aa+aa+bb;
					xx=xx+aa+bb-xx%(aa+bb)+yy;
					if(xx<=tt)res=xx;
				}
				if((res)<d[y])
				{
					d[y]=res;
					q.push({y,d[y]});
				}
			}
		}
	}
	printf("Case %lld: %lld\n",cnt++,d[tt]);
}
void solve()
{
	for(int i=1;i<=m*3;i++)ne[i]=0,h[i]=0;
	idx=1;
	while(m--)
	{
		int u,v,a,b,t;
		cin>>u>>v>>a>>b>>t;
		add(u,v,a,b,t);
		add(v,u,a,b,t);
	}
	djstla();
}
signed main()
{
	while(cin>>n>>m>>ss>>tt)
	{
		solve();
	}
	return 0;
}
//3 2 1 3 
//1 2 5 6 3 
//2 3 7 7 6 
//3 2 1 3 
//1 2 5 6 3 
//2 3 9 5 6