#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson (k << 1) | 1
#define debug cout << 666 << endl;
using namespace std;
const int N = 1e6 + 5;
int a[5][20];
int st[N];
int x, y;
typedef pair<int,int>PII;
typedef array<int,3>ar;
typedef array<int,4>ar4;
vector<ar4>E[N];
int dis[N];
int n,m;
int cn=0;
void dij(int s)
{
    for(int i=1;i<=n;i++) dis[i]=1e18,st[i]=0;
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0,s});
    dis[s]=0;
    while(q.size()!=0)
    {
        auto P=q.top();
        q.pop();
        int u=P.second;
        if(st[u]==1) continue;
        st[u]=1;
        for(auto V:E[u])
        {
            int w=V[3];
            int v=V[0];
            int a=V[1];
            int b=V[2];
            int now=(dis[u])%(a+b);
            if(w>a) continue;
            int dti=0;
            if(now>a)
            {
                dti=a+b-now+1;
                dti+=w;
            }
            else 
            {
                int ne=a-now;
                if(w>ne)
                {
                    dti=ne+b+w;
                }
                else dti=w;
            }
            if(dis[v]>dis[u]+dti)
            {
                dis[v]=dis[u]+dti;
                q.push({dis[v],v});
            }
        }
    }
}
void vision()
{
    int s,t;
    while (cin >> n >> m>>s>>t)
    {
        for(int i=1;i<=m;i++)
        {
            int u,v,w,a,b;
            cin>>u>>v>>a>>b>>w;
            E[u].push_back({v,a,b,w});
            E[v].push_back({u,a,b,w});
        }
        dij(s);
        cout<<"Case "<<++cn<<": ";
        cout<<dis[t]<<"\n";
        for(int i=1;i<=n;i++) E[i].clear();
    }
    return;
}
signed main()
{
     ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        vision();
    }
    return 0;
}