#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
using std::priority_queue;
using std::pair;
using std::vector;
using std::make_pair;
using std::greater;
using std::less;

#define rint register int
#define inf 0x3f3f3f3f
#define pa pair<int,int>
const int maxn = 305;
const int maxm = 50005;
typedef long long ll;

struct edge{
	int v,nxt,w;
	int open,close;
} e[maxm];
int n,m,s,t,head[maxn],tot,dis[maxn],Orz;
bool conf[maxn];
priority_queue <pa,vector<pa>,greater<pa> > dij;

inline int read();
void add(int u,int v,int a,int b,int t){e[++tot].close=b;e[tot].open=a;e[tot].v=v;e[tot].w=t;e[tot].nxt=head[u];head[u]=tot;}

int main(){
	while(scanf("%d %d %d %d",&n,&m,&s,&t)!=EOF){++Orz;tot=0;
		for(rint i=1;i<=n;++i)
		head[i]=0;
		for(rint i=0;i<maxm;++i)
		e[i].v=e[i].nxt=e[i].w=e[i].open=e[i].close=0;
		for(rint i=1;i<=n;++i)dis[i]=inf,conf[i]=false;
		for(rint i=1;i<=m;++i){
			int a=read(),b=read(),c=read(),d=read(),e=read();
			if(c>=e)
			add(a,b,c,d,e);
		}
		dis[s]=0;
		dij.push(make_pair(0,s));
		while(dij.size()){
			int u = dij.top().second;dij.pop();
			if(conf[u])continue;
			conf[u]=true;
			for(rint i = head[u];i;i=e[i].nxt){
				int v = e[i].v;
				int sum = e[i].close + e[i].open;
				int k = dis[u]%sum;
				int spend = 0;
				if(k + e[i].w > e[i].open)spend = sum - k + e[i].w;
				else spend = e[i].w;
				spend += dis[u];
				if(dis[v] > spend){
					dis[v] = spend;
					dij.push(make_pair(dis[v],v));
				}
			}
		}
		while(dij.size())dij.pop();
		printf("Case %d: %d\n",Orz,dis[t]);
	}
    return 0;
}

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}