#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
struct route {
int deb,fin,vitesse,longueur;
};
struct pos {
double temps;
int num_ville,vitesse_avant;
int ville_avant,vitesse_encore_avant;
bool operator<(const pos& autre) const {
return temps<autre.temps;
}
};
const int VILLEMAXI=152,VITESSEMAXI=502;
vector<int> adja[VILLEMAXI];
vector<route> routes;
set<pos> encours;
double dist[VILLEMAXI][VITESSEMAXI];
pair<int,int> avant[VILLEMAXI][VITESSEMAXI]; // ville,vitesse
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int nbvilles,nbroutes,destination;
cin>>nbvilles>>nbroutes>>destination;
for (int i=0;i<nbroutes;i++){
route r;
cin>>r.deb>>r.fin>>r.vitesse>>r.longueur;
routes.push_back(r);
adja[r.deb].push_back(i);
}
for (int i=0;i<nbvilles;i++){
for (int j=0;j<VITESSEMAXI;j++){
dist[i][j]=-1;
}
}
encours.insert({0,0,70,-1,-1});
//int compt=0;
bool ok=false;
int vitessefin=0;
while (ok==false){
//compt++;
pos ec=*encours.begin();
encours.erase(encours.begin());
if (ec.num_ville==destination){
dist[ec.num_ville][ec.vitesse_avant]=ec.temps;
vitessefin=ec.vitesse_avant;
avant[ec.num_ville][ec.vitesse_avant]={ec.ville_avant,ec.vitesse_encore_avant};
ok=true;
}
else {
if (dist[ec.num_ville][ec.vitesse_avant]==-1){
dist[ec.num_ville][ec.vitesse_avant]=ec.temps;
avant[ec.num_ville][ec.vitesse_avant]={ec.ville_avant,ec.vitesse_encore_avant};
for (auto v:adja[ec.num_ville]){
int nouv_vitesse=ec.vitesse_avant;
if (routes[v].vitesse!=0){
nouv_vitesse=routes[v].vitesse;
}
pos nouv;
nouv.temps=ec.temps+(double)routes[v].longueur/(double)nouv_vitesse;
nouv.num_ville=routes[v].fin;
nouv.vitesse_avant=nouv_vitesse;
nouv.ville_avant=ec.num_ville;
nouv.vitesse_encore_avant=ec.vitesse_avant;
if (dist[nouv.num_ville][nouv.vitesse_avant]==-1){
encours.insert(nouv);
}
}
}
}
}
//cout<<42<<endl;
//return 0;
vector<int> rep={};
int ville_ec=destination,vitesse_ec=vitessefin;
while (ville_ec!=0){
rep.push_back(ville_ec);
int nvil=avant[ville_ec][vitesse_ec].first;
int nvit=avant[ville_ec][vitesse_ec].second;
ville_ec=nvil;
vitesse_ec=nvit;
}
rep.push_back(0);
reverse(rep.begin(),rep.end());
for (auto r:rep){
cout<<r<<" ";
}
cout<<endl;
//cout<<dist[destination][vitessefin]<<endl;
return 0;
}
