#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 50050
using namespace std;
typedef struct node
{
long long cost;
int id, a, b, next;
}node;

int s, e;
node edge[3 * N];
int t, head[505];
long long cost[505];

void addedge(int u, int v, int a, int b, long long c)
{
  edge[t].id = v;
  edge[t].a  = a;
  edge[t].b  = b;
  edge[t].cost = c;
  edge[t].next = head;
  head  = t++;
}

void SPFA()
{
  int cur, at, need;
  queue<int>q;
  bool visited[505];
  memset(visited, true, sizeof(visited));
  for(int i = 0; i < 505; i++)
        cost = LINF;

  q.push(s);
  cost = 0; visited = false;

  while(!q.empty())
  {
    cur = q.front();
    q.pop();
    visited[cur] = true;

    for(int e = head[cur]; e != -1; e = edge[e].next)
    {
        at = cost[cur] % (edge[e].a + edge[e].b);
      
        if(edge[e].a - edge[e].cost >= at){
               need = cost[cur] + edge[e].cost;
        }else{
              need = cost[cur] + (edge[e].a + edge[e].b - at) + edge[e].cost;
        }

        if(cost[edge[e].id] > need)
        {
          cost[edge[e].id] = need;
          if(visited[edge[e].id])
          {
              visited[edge[e].id] = false;
              q.push(edge[e].id);
          }
        }
    }
  }
}

int main()
{
    int ncase(1), n, m;
    int u, v, a, b, c;
    while(~scanf("%d%d%d%d", &n, &m, &s, &e))
    {
      t = 0;
      memset(head, -1, sizeof(head));
      for(int i = 0; i < m; i++)
      {
        scanf("%d%d%d%d%d", &u, &v, &a, &b, &c);
        if(a >= c)
            addedge(u, v, a, b, c);
      }
      SPFA();
      printf("Case %d: %lld\n", ncase++, cost[e]);
    }  
    return 0;
}

#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 50050
using namespace std;
typedef struct node
{
long long cost;
int id, a, b, next;
}node;

int s, e;
node edge[3 * N];
int t, head[505];
long long cost[505];

void addedge(int u, int v, int a, int b, long long c)
{
  edge[t].id = v;
  edge[t].a  = a;
  edge[t].b  = b;
  edge[t].cost = c;
  edge[t].next = head;
  head  = t++;
}

void SPFA()
{
  int cur, at, need;
  queue<int>q;
  bool visited[505];
  memset(visited, true, sizeof(visited));
  for(int i = 0; i < 505; i++)
        cost = LINF;

  q.push(s);
  cost = 0; visited = false;

  while(!q.empty())
  {
    cur = q.front();
    q.pop();
    visited[cur] = true;

    for(int e = head[cur]; e != -1; e = edge[e].next)
    {
        at = cost[cur] % (edge[e].a + edge[e].b);
      
        if(edge[e].a - edge[e].cost >= at){
               need = cost[cur] + edge[e].cost;
        }else{
              need = cost[cur] + (edge[e].a + edge[e].b - at) + edge[e].cost;
        }

        if(cost[edge[e].id] > need)
        {
          cost[edge[e].id] = need;
          if(visited[edge[e].id])
          {
              visited[edge[e].id] = false;
              q.push(edge[e].id);
          }
        }
    }
  }
}

int main()
{
    int ncase(1), n, m;
    int u, v, a, b, c;
    while(~scanf("%d%d%d%d", &n, &m, &s, &e))
    {
      t = 0;
      memset(head, -1, sizeof(head));
      for(int i = 0; i < m; i++)
      {
        scanf("%d%d%d%d%d", &u, &v, &a, &b, &c);
        if(a >= c)
            addedge(u, v, a, b, c);
      }
      SPFA();
      printf("Case %d: %lld\n", ncase++, cost[e]);
    }  
    return 0;
}