// #pragma GCC optimize(2)  //O2优化开启
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
typedef unsigned long long ull;

set<int> dist[310];
int n, m, s, ed;
int tp;
struct node {
    int x, a, b, t;
};

vector<node> e[310];

void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, s});
    dist[s].insert(0);
    while (q.size()) {
        int ti = q.top().fi, ver = q.top().se;
        q.pop();
        for (auto &[j, a, b, t] : e[ver]) {
            if (a < t) {
                continue;
            }
            int tt = ti % (a + b);
            int time;
            if (tt + t <= a) {
                time = ti + t;
            } else {
                time = ti - tt + a + b + t;
            }
            if (time > 61000) {
                continue;
            }
            if (!dist[j].count(time)) {
                dist[j].insert(time);
                q.push({time, j});
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while (cin >> n >> m >> s >> ed) {
        for (int i = 1; i <= n; i++) {
            dist[i].clear();
            e[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int u, v, a, b, t;
            cin >> u >> v >> a >> b >> t;
            e[u].push_back({v, a, b, t});
        }
        dijkstra();
        int ans = *dist[ed].begin();
        printf("Case %lld: %lld\n", ++tp, ans);
    }
}