#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st string
#define ld long double
#define ch char
typedef unsigned long long ull;
const int N = 155, M = 505;
bool vis[N][M];
double dis[N][M];
pair <int, int> from[N][M];
int f[N], cnt, n, m, ed, u, v, p, w, l;

struct node {
	int to, next, p, w;
} edge[N * N];

inline void spfa() {
	queue<pair<int, int>>q;
	dis[0][70] = 0;
	q.push(make_pair(0, 70));
	while (!q.empty()) {
		int u = q.front().first, speed = q.front().second;
		q.pop();
		vis[u][speed] = 0;
		for (int i = f[u]; i; i = edge[i].next) {
			int v = edge[i].to, w = edge[i].w, xs = edge[i].p;
			if (!xs && dis[u][speed] + 1.0 * w / speed < dis[v][speed]) {
				dis[v][speed] = dis[u][speed] + 1.0 * w / speed;
				from[v][speed] = make_pair(u, speed);
				if (!vis[v][speed]) {
					q.push(make_pair(v, speed));
					vis[v][speed] = 1;
				}
			}
			if (xs && dis[u][speed] + 1.0 * w / xs < dis[v][xs]) {
				dis[v][xs] = dis[u][speed] + 1.0 * w / xs;
				from[v][xs] = make_pair(u, speed);
				if (!vis[v][xs]) {
					q.push(make_pair(v, xs));
					vis[v][xs] = 1;
				}
			}
		}
	}
}

inline void clear() {
	for (int i = 1 ; i <= N; i++) {
		for (int j = 1 ; j <= M ; j++) {
			dis[i][j] = 0x3f3f3f3f;
		}
	}
}

inline void add(int u, int v, int p, int w) {
	edge[++cnt] = node{v, f[u], p, w};
	f[u] = cnt;
}

inline void print(int u, int xs) {
	if (u) {
		print(from[u][xs].first, from[u][xs].second);
	}
	cout << u << " ";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> ed;
	for (int i = 1 ; i <= m ; i++) {
		cin >> u >> v >> p >> w;
		add(u, v, p, w);
	}
	clear();
	spfa();
	int ans = 0;
	for (int i = 1 ; i <= 500 ; i++) {
		if (dis[ed][i] < dis[ed][ans]) {
			ans = i;
		}
	}
	print(ed, ans);
	return 0;
}