// 分层图最短路 Dijkstra 算法 O(Mlog(NV))
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N=155,M=22505;
int idx,h[N],to[M],ne[M],V[M],L[M];
void add(int a,int b,int v,int l){
  to[++idx]=b;V[idx]=v;L[idx]=l;ne[idx]=h[a];h[a]=idx;
}
int n,m,T;
double d[N][505]; int vis[N][505]; pii pre[N][505];

void dijkstra(int s){
  priority_queue<pair<double,pii>> q; //大根堆
  memset(d,126,sizeof d); d[1][70]=0;
  pre[1][70]={0,0};
  q.push({0,{1,70}});
  while(q.size()){
    auto [x,v]=q.top().second; q.pop();
    if(vis[x][v]) continue; vis[x][v]=1;
    for(int i=h[x]; i; i=ne[i]){
      int y=to[i],l=L[i];
      if(V[i]==0 && d[y][v]>d[x][v]+1.0*l/v){ //当前边的限速=0时，取上一条边的速度松弛
        d[y][v]=d[x][v]+1.0*l/v;
        pre[y][v]={x,v};          //记录前驱点
        q.push({-d[y][v],{y,v}}); //当前点的状态入队
      }
      if(V[i] && d[y][V[i]]>d[x][v]+1.0*l/V[i]){ //当前边的限速>0时，取当前边的速度松弛
        d[y][V[i]]=d[x][v]+1.0*l/V[i];
        pre[y][V[i]]={x,v};
        q.push({-d[y][V[i]],{y,V[i]}});
      }
    }
  }
}
void output(int p,int v){
  if(p==0) return;
  output(pre[p][v].first,pre[p][v].second);
  printf("%d ",p-1);
}
int main(){
  cin>>n>>m>>T; T++;
  for(int i=1,a,b,v,l; i<=m; i++){
    cin>>a>>b>>v>>l;
    a++,b++; add(a,b,v,l);
  }
  
  dijkstra(1);
  int v=distance(d[T],min_element(d[T],d[T]+505)); //找出终点最短路的限速
  output(T,v); //回溯输出路径
}