#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],FAT[NM];

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

int main()
{
    char isin[NM];

    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;

    memset(isin,0,sizeof(isin));

    COST[S]=0;
    Q.push(S);
    isin[S]=1;

    while(!Q.empty())
    {
         int nod=Q.front();
         Q.pop();
         isin[nod]=0;

         if(isin[FAT[nod]]) continue;

         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;
                  FAT[nnod]=FAT[nod];
                  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;
}