#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define pre(x,a,b) for(int x=a;x>=b;x--)
#define endl "\n"
#define pb push_back
#define ll long long
#define int long long
#define pii pair<ll,ll>
#define psi pair<string, ll>
#define de cout<<1;
#define mem(a,x) memset(a,x,sizeof a)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int mod1=998244353;
const int mod2=1e9+7;
const int INF=1e18;
const int N = 1e6 + 60;
int number;
int n,m,s,te,idx;
struct we{
    int t,id;
    bool operator <(const we &k)const{
        return k.t<t;
    }
};
int dis[500];
struct wwe{
    int w,a,b,t;
};
vector<wwe>ve[305];
int c[500];
void bfs()
{
    for(int i=1;i<=n;i++)dis[i]=1e18,c[i]=0;
    dis[s]=0;
    priority_queue<we>q;
    q.push({0,s});

    while(q.size()){
        we now=q.top();
        q.pop();
        if(c[now.id])continue;
        c[now.id]=1;
        for(auto [j,a,b,p]:ve[now.id]){
            int tt=dis[now.id];
            int mm=tt%(a+b);
            if(mm<a&&mm+p<=a&&dis[now.id]+p<dis[j]){
                dis[j]=dis[now.id]+p;
                q.push({dis[j],j});
            }
            else if(p<=a&&dis[now.id]+(a+b-mm+p)<dis[j]){
                dis[j]=dis[now.id]+(a+b-mm+p);
                q.push({dis[j],j});
            }
        }
    }
    //cout<<dis[2];
    cout << "Case " << idx<<": ";
    cout<<dis[te]<<"\n";

}



void solve()
{
    while(cin >> n >> m>>s>>te)
    {
        idx++;
        for(int i=1;i<=m;i++){
            int l,r,a,b,t;
            cin>>l>>r>>a>>b>>t;
            ve[l].push_back({r,a,b,t});
            ve[r].push_back({l,a,b,t});
        }
        bfs();
        for(int i=1;i<=n;i++)ve[i].clear();
    }
}
signed main()
{
	IOS;
	int _;
	//scanf("%d", &_);
	_ = 1;
	while(_ -- )
	{
		number++;
		solve();
	}
	return 0;
}