#include<fstream>
#define Nmax 5001
#define infinit 2000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijcstra.out");

int n,xi,viz[Nmax],pre[Nmax];
double c[Nmax][Nmax],dist[Nmax];

void citire()
{int i,j,x,y,m;
double cost;
fin>>n>>m>>xi;
for(i=1;i<=n;i++)
  for(j=i;j<=n;j++)
    {c[i][j]=infinit;
     c[j][i]=infinit;
    }
for(i=1;i<=n;i++)
   {dist[i]=infinit;
    c[i][i]=0;
   }
for(i=1;i<=m;i++)
 {fin>>x>>y>>cost;
  c[x][y]=cost;
 }
}

void dijkstra()
{int i,j,v;
double min;
dist[xi]=0;
pre[xi]=0;
for(i=1;i<n;i++)
  {min=infinit;
     for(j=1;j<=n;j++)
       if(!viz[j] && dist[j]<min)
         {v=j;
          min=dist[j];
         }
  viz[v]=1;
  for(j=1;j<=n;j++)
    if(dist[j]>dist[v]+c[v][j])
      {dist[j]=dist[v]+c[v][j];
       pre[j]=v;
      }
  }
}

int main()
{citire();
dijkstra();
for(int i=1;i<=n;i++)
 fout<<dist[i]<<" ";
fin.close();
fout.close();
return 0;
}