#include<iostream>
#include<string.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<set>
#include<bitset>
#include<deque>
#include<unordered_map>
#include<algorithm>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=305,M=5e2+10;
int n,m,x,y;
int dist[305],st[305];

struct le{
	int y,a,b,t;
};
vector<le>v[N];
void get(){
	priority_queue<int,vector<int>,greater<int>>q;
	for(int i=1;i<=n;i++){
		dist[i]=1e9,st[i]=0;
	}
	q.push(x);
	dist[x]=0;
	while(q.size()){
		auto u=q.top();
		q.pop();
		if(st[u]) continue ;
		st[u]=1;
		for(int i=0;i<v[u].size();i++){
			int oo=v[u][i].y;
			int a=v[u][i].a;
			int b=v[u][i].b;
			int t=v[u][i].t;
			int tt=0;
			if(a<t) continue ;
			if(a>=t){
				tt=dist[u]%(a+b);
				if(tt>a) tt=a+b-tt+t;
				else{
					if(tt+t<=a) tt=t;
					else if(tt+t<=a+b) tt=a+b-tt+t;
				}
			}
			if(dist[oo]>dist[u]+tt){
				dist[oo]=dist[u]+tt;
				q.push(oo);
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int o=0;
	while(cin>>n>>m>>x>>y){
		for(int i=1;i<=m;i++){
			int u,vv,a,b,t;
			cin>>u>>vv>>a>>b>>t;
			v[u].push_back({vv,a,b,t});
		}
		get();
		cout<<"Case "<<++o<<": "<<dist[y]<<endl;
	}
	return 0;
	
}