#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int dist[N];
struct stu
{
    int y, a, b, t;
};
vector<stu> g[N];
bool st[N];

void ffff(int root, int ende)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[root] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, root});
    while (q.size())
    {
        auto t = q.top();
        q.pop();

        int Dist = t.first, id = t.second;
        if (st[id])
            continue;
        // cout << Dist << ' ' << id << '\n';
        st[id] = true;
        for (auto [y, a, b, t] : g[id])
        {
            if (t > a)
                continue;
            int u = Dist % (a + b);
            if (u + t <= a)
            {
                if (dist[y] > Dist + t)
                {
                    dist[y] = Dist + t;
                    q.push({dist[y], y});
                }
            }
            else
            {
                if (dist[y] > Dist + a + b - u + t)
                {
                    dist[y] = Dist + a + b - u + t;
                    q.push({dist[y], y});
                }
            }
            // int time_len = a + b;
            // int time_cnt = (Dist + time_len - 1) / time_len;
        }
    }
}

signed main()
{
    int Case = 0;
    int n, m, s, t;
    while (cin >> n >> m >> s >> t)
    {
        Case++;
        int u, v, a, b, tt;
        for (int i = 1; i <= n; i++)
            g[i].clear();
        for (int i = 1; i <= m; i++)
        {
            cin >> u >> v >> a >> b >> tt;
            g[u].push_back({v, a, b, tt});
        }
        ffff(s, t);
        cout << "Case " << Case << ": " << dist[t] << '\n';
    }

    return 0;
}