// #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;

int n, m, st, ed;
int tp;
set<PII> bj;
set<int> ans;

struct node {
    int x, a, b, t;
};

vector<node> e[310];

void dfs(int ver, int ti) {
    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 (!bj.count({j, time})) {
            if (j == ed) {
                ans.insert(time);
            }
            bj.insert({j, time});
            dfs(j, time);
        }
    }
}

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

    while (cin >> n >> m >> st >> ed) {
        for (int i = 1; i <= n; i++) {
            e[i].clear();
        }
        bj.clear();
        ans.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});
        }
        if (st == ed) {
            printf("Case %lld: %lld\n", ++tp, 0);
        }
        dfs(st, 0);
        int an;
        for (auto &i : ans) {
            an = i;
            break;
        }
        printf("Case %lld: %lld\n", ++tp, an);
    }
}