#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e12+99;
const int N=1e3+9;
int st[N],d[N];
int n,m,s,t,idx;
struct PII{
	int d,a,b;
}g[N][N];
void init()
{
	for(int i=1;i<=n;i++)
	{
		st[i]=0,d[i]=inf;
		for(int j=1;j<=n;j++)
		{
			g[i][j].d=inf;
			g[i][j].a=inf;
			g[i][j].b=inf;
		}
	}
}
int dic(int d,int idx,int next)
{
	int x=g[idx][next].a,y=g[idx][next].b;
	int sum=x+y;
	sum=d%sum;
	if(sum+g[idx][next].d<=x)
	{
		return g[idx][next].d+d;
	}
	else
	{
		int res=d+x+y-sum;
		res+=g[idx][next].d;
		return res;	
	}
}
void djstl(int x)
{
	d[s]=0;
	while(x--)
	{
		int t=-1;
		for(int i=1;i<=n;i++)
		{
//			printf("i=%lld t=%lld d[t]=%lld\n",i,t,d[t]);
			if(st[i]==0&&(t==-1||d[i]<d[t]))
			{
				t=i;
			}
		}
		st[t]=1;
		for(int i=1;i<=n;i++)
		{
//			printf("t=%lld i=%lld dic=%lld\n",t,i,dic(d[t],t,i));
			if(g[t][i].d!=inf)
			d[i]=min(d[i],dic(d[t],t,i));
		}
//		printf("t=%lld\n",t);
//		for(int i=1;i<=n;i++)printf("%lld ",d[i]);
//		printf("\n");
	}
	int ans=d[t];
	printf("Case %lld: %lld\n",++idx,ans);
}
void solve()
{
	
	init();
	while(m--)
	{
		int x,y,d,a,b;
		cin>>x>>y>>a>>b>>d;
		g[x][y]=g[y][x]={d,a,b};
	}
	djstl(n);
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	while(cin>>n>>m>>s>>t)
	{
		solve();
	}
}