#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;
};
vector<PII>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].clear();
		}
	}
}
int dic(int d,int tt,int a,int b)
{
	int x=a,y=b;
	int sum=x+y;
	sum=d%sum;
	if(sum+tt<=x)
	{
		return tt+d;
	}
	else
	{
		int res=d+x+y-sum;
		res+=tt;
		return res;	
	}
}
int mmin(int x,int y,int d)
{
	int res=inf;
	for(auto&x:g[x][y])
	{
		res=min(res,dic(d,x.d,x.a,x.b));
	}
	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));
			d[i]=min(d[i],mmin(t,i,d[t]));
		}
//		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;
		PII tt={d,a,b};
		g[x][y].push_back(tt);
		g[y][x]=g[x][y];
	}
	djstl(n);
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	while(cin>>n>>m>>s>>t)
	{
		solve();
	}
}