#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[maxn],used[maxn],next[maxn],first[maxn];

 int n,m,ecnt,s,t;

 struct edge{

     int v,a,b,t;

 } e[maxn];

 void addedge(int u,int v,int a,int b,int t){

     next[++ecnt]=first[u];

     e[ecnt].v=v;

     e[ecnt].a=a;

     e[ecnt].b=b;

     e[ecnt].t=t;

     first[u]=ecnt;

 }

 void dijkstra(int s){

     for(int i=;i<=n;i++) d[i]=INF;

     d[s]=;

     memset(used,,sizeof(used));

     for(int k=;k<=n;k++){

         int u,m=INF;

         for(int i=;i<=n;i++) if(!used[i]&&d[i]<m) m=d[u=i];

         used[u]=;

         for(int i=first[u];i!=-;i=next[i]){

             int v=e[i].v,a=e[i].a,b=e[i].b,t=e[i].t;

             if(a<t) continue;//打开的时间小于通过的时间 

             int now=d[u]%(a+b);

             if(now+t<=a){//现在能够通过的情况下松弛

                 if(d[v]>d[u]+t) d[v]=d[u]+t;

             }

             else{

                 int wait=a+b-now;//现在需要等待的情况下松弛

                 if(d[v]>d[u]+wait+t) d[v]=d[u]+wait+t;

             }

         }

     }    

 }

 int main(){

     int kase=;

     while(scanf("%d %d %d %d",&n,&m,&s,&t)!=EOF){

         memset(first,-,sizeof(first));

         ecnt=;

         while(m--){

             int u,v,a,b,t;

             cin>>u>>v>>a>>b>>t;

             addedge(u,v,a,b,t);

         }

         dijkstra(s);

         printf("Case %d: ",++kase);

         printf("%d\n",d[t]);

     }

     return ;

 }