#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define ll long long

const int N = 1e3 + 20;
ll dis[N];
struct node
{
    int v;
    ll a,b,t;
} ;
vector<node> g[N];
int n,m,ss,tt;
void solve()
{
    for(int i = 0; i <= n; i++) dis[i] = 1e18,g[i].clear();
    while(m--)
    {
        int u,v;
        ll a,b,t;
        cin >> u >> v >> a >> b >> t;
        if(a < t) continue;
        g[u].push_back({v,a,b,t});
    }
    
    dis[ss] = 0;
    queue<int> q;
    q.push(ss);
    ll ans = 1e18;

    while(q.size())
    {
        int u = q.front();
        q.pop();

        for(int i = 0; i < (int)g[u].size(); i++)
        {
            node j = g[u][i];
            ll term = j.a + j.b;
            if(dis[u] % term + j.t <= j.a)
            {
                dis[j.v] = min(dis[u] + j.t,dis[j.v]);
            }
            else 
            {
                dis[j.v] = min(dis[u] + (term - dis[u] % term) + j.t,dis[j.v]);
            }
            q.push(j.v);
            if(j.v == tt) ans = min(ans,dis[tt]);
        }
    }
    cout << ans << "\n";
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	// cin >> T;
	while(cin >> n >> m  >> ss >> tt)
	{
        cout << "Case " << T++ << ": " ;
		solve();
	}
    return 0;
}