#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

#define NM 50005
#define inf 2000000000
#define PB push_back
#define MKP make_pair

int N,M,S,COST[NM];

vector<pair<int,int> > G[NM];

queue<int> Q;

char isin[NM];

int main()
{
    int start=clock();
    
    int a,b,c;
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d %d",&N,&M,&S);
    
    S=1;
    
    for(int i=1;i<=M;++i)
    {
        scanf("%d %d %d",&a,&b,&c);    
        G[a].PB(MKP(b,c));
    }
    
    for(int i=1;i<=N;++i)
       COST[i]=inf;
    
    COST[S]=0;
    Q.push(S);
    isin[S]=1;
    
    while(!Q.empty())
    {
         int nod=Q.front();
         Q.pop();
         isin[nod]=0;
         
         for(int i=0;i<G[nod].size();++i)
         {
              int nnod=G[nod][i].first;
              int ncost=G[nod][i].second;
              
              if(COST[nnod]>COST[nod]+ncost)
              {
                  COST[nnod]=COST[nod]+ncost;
                  if(!isin[nnod])
                  {
                       Q.push(nnod);
                       isin[nnod]=1;          
                  }                          
              }   
         }            
    }
    
    for(int i=2;i<=N;++i)
       if(COST[i]==inf) printf("0 ");
       else printf("%d ",COST[i]);
    
    int stop=clock();
    
    //printf("\n%lf",(double)(stop-start)/CLOCKS_PER_SEC);   
    
    return 0;
}