#include <stdio.h>
#include <stdlib.h>
#define inf 9999
int vis[10005]={0};//标记
int dis[10005]={9999};//累计路程
int dis_point[10005][10005];
int point_direct[10005][10005];//用0 1表示点与点的路径存在与否
int n,m,s;
int check()
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
            return 0;
    }
    return 1;
}
void init_chart(int stx)
{
    vis[stx]=1;
    dis[stx]=0;
}
void dijkstra(int stx)
{
  if(check())
  {
    for(int i=1;i<=n;i++)
    printf("%d ",dis[i]);
  }
  else
  {
  for(int j=1;j<=n;j++)//更新部分
  {

    if(point_direct[stx][j]&&j!=stx&&!vis[j])
      {
 int temp_dis=dis_point[stx][j]+dis[stx];
      if(temp_dis<dis[j])
      {
          dis[j]=temp_dis;
      }
      }
  }
  int min=inf,pos=1;
  for(int i=1;i<=n;i++)
  {
      if(dis[i]<min&&!vis[i]&&i!=stx)
      {
          min=dis[i];
          pos=i;
      }
  }//找到已经找到的节点的最小的那个
   vis[pos]=1;
   dijkstra(pos);
  }
}
int main()
{
  memset(point_direct,0,sizeof(point_direct));
  scanf("%d %d %d",&n,&m,&s);
  int u,v,w,temp=m;
  while(temp--)
  {
      scanf("%d %d %d",&u,&v,&w);
      dis_point[u][v]=w;
      point_direct[u][v]=1;
  }
  init_chart(s);
  dijkstra(s);
}