#include<bits/stdc++.h>
using namespace std;
const int MAXN=350;
int n,m,s,t;
vector<int>ver[MAXN];
vector<int>edge[MAXN];
vector<int>a[MAXN],b[MAXN];
bool vis[MAXN];
int d[MAXN];
int T;
struct Node
{
    int pos,dis;
    bool operator < (const Node &x) const
    {
        return x.dis<dis;
    }
};
inline int read()
{
    int tot=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
    {
        tot=tot*10+c-'0';
        c=getchar();    
    }
    return tot;
}
inline void dijkstra()
{
    priority_queue<Node>q;
    while(q.size())q.pop();
    q.push((Node){s,0});
    d[s]=0;
    while(q.size())
    {
        Node now=q.top();
        q.pop();
        int x=now.pos,y=now.dis;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=0;i<ver[x].size();i++)
        {
            int tt=ver[x][i];
            int res=y%(a[x][i]+b[x][i]);
            if(res>=a[x][i])
            {
                if(res-a[x][i]==0&&b[x][i]+edge[x][i]+y<d[tt])
                {
                    d[tt]=b[x][i]+edge[x][i]+y;
                    if(!vis[tt])q.push((Node){tt,d[tt]});
                }
                else if(res-a[x][i]>0&&b[x][i]-(res-a[x][i])+edge[x][i]+y<d[tt])
                {
                    d[tt]=b[x][i]-(res-a[x][i])+edge[x][i]+y;
                    if(!vis[tt])q.push((Node){tt,d[tt]});
                }
            }
            else
            {
                if(a[x][i]-res>=edge[x][i]&&edge[x][i]+y<d[tt])
                {
                    d[tt]=edge[x][i]+y;
                    if(!vis[tt])q.push((Node){tt,d[tt]});
                }
                else if(a[x][i]-res<edge[x][i]&&edge[x][i]+y+b[x][i]+a[x][i]-res<d[tt])
                {
                    d[tt]=edge[x][i]+y+b[x][i]+a[x][i]-res;
                    if(!vis[tt])q.push((Node){tt,d[tt]});
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        memset(d,0x3f,sizeof(d));
        for(int i=1;i<=n;i++)
        {
            ver[i].clear();edge[i].clear();
            a[i].clear();b[i].clear();
        }
        for(int i=1;i<=m;i++)
        {
            int x1=read(),x2=read(),x4=read(),x5=read(),x3=read();
            if(x3>x4)continue;
            ver[x1].push_back(x2);
            edge[x1].push_back(x3);
            a[x1].push_back(x4);
            b[x1].push_back(x5);
        }
        //cout<<d[t]<<endl;
        dijkstra();
        printf("Case %d: %d\n",++T,d[t]);
    }
    return 0;
}