/* https://arena.olimpiici.com/#/catalog/756/problem/101958 */

#include <iostream>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

struct Path {
	unsigned long long b;
	unsigned long long s;
	unsigned long long g;
	unsigned long long r;
};

int main() {
	unsigned long long N, M, S;
	cin >> N >> M >> S;
	vector<vector<Path>> crossroads(N+1);
	for (long long i = 0; i < M; i++) {
		unsigned long long ai, bi, si, gi, ri;
		cin >> ai >> bi >> si >> gi >> ri;
		crossroads[ai].push_back({ bi, si, gi, ri });
		crossroads[bi].push_back({ ai, si, gi, ri });
	}

	// Dijkstra
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
	vector<long> dist(N+1, -1);
	vector<bool> visited(N+1, false);

	q.push({ S, 1 });
	while (!q.empty()) {
		long long currTime = q.top().first;
		long long currNode = q.top().second;
		q.pop();

		visited[currNode] = true;
		for (Path& p : crossroads[currNode]) {
			unsigned long long waitingTime = (currTime % (p.g + p.r) < p.g) ? 0 : p.g + p.r - (currTime % (p.g + p.r));
			if (!visited[p.b] && (dist[p.b] < 0 || currTime + p.s + waitingTime < dist[p.b])) {
				dist[p.b] = currTime + p.s + waitingTime;
				q.push({ dist[p.b], p.b });
			}
		}
	}


	for (long long i = 2; i <= N; i++) {
		cout << dist[i] << " ";
	}
}