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

struct node
{
	int t, pos, from;
	bool operator < (const node k) const
	{
		if (t != k.t)
		{
			return t > k.t;
		}
		return pos > k.pos;
	}
};

int tt = 1;
void solve(int n, int m, int S, int T)
{
	vector <vector <pair <pii, pii> > > s(n + 1); // v a b t
	for (int i = 1; i <= m; i++)
	{
		int u, v, a, b, t;
		cin >> u >> v >> a >> b >> t;
		if (t <= a)
			s[u].push_back({{v, a}, {b, t}});
	}
	priority_queue <node> q;
	q.push({0, S, 0});
	vector <vector <int>> dist(n + 1, vector <int>(n + 1, 0x3f3f3f3f3f3f3f3f)), box(n + 1, vector <int>(n + 1));
	int ans = 0;
	while (!q.empty())
	{
		node now = q.top();
		q.pop();
		if (now.pos == T)
		{
			ans = now.t;
		}
		if (box[now.pos][now.from])
			continue;
		box[now.pos][now.from] = 1;
		for (auto [i, j] : s[now.pos])
		{
			if (box[i.first][now.pos])
				continue;
			int tim = now.t - now.t / (i.second + j.first) * (i.second + j.first) + j.second;
			if (tim <= i.second)
			{
				if (now.t + j.second < dist[i.first][now.pos])
				{
					dist[i.first][now.pos] = now.t + j.second;
					q.push({dist[i.first][now.pos], i.first});
				}
			}
			else
			{
				int xx = (now.t / (i.second + j.first) + 1) * (i.second + j.first) + j.second;
				if (xx < dist[i.first][now.pos])
				{
					dist[i.first][now.pos] = xx;
					q.push({xx, i.first});
				}
			}
		}
	}
	cout << "Case " << tt++ << ": ";
	cout << ans << "\n";
}

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

	int n, m, s, t;
	while (cin >> n >> m >> s >> t)
	{
		solve(n, m, s, t);
	}
	return 0;
}