using namespace std;
const int MAX=1e5+10;
int n,m,s,dis[MAX];
bool vis[MAX];
struct node
{
  int to,val;
};
vector <node> G[MAX];
void add(int x,int y,int z)
{
  node p;
  p.to=y;
  p.val=z;
  G[x].push_back(p);
}
queue<int> q;
int main()
{
  cin>>n>>m>>s;
  while(m--)
  {
    int u,v,w;
    cin>>u>>v>>w;
    add(u,v,w);
  }
  memset(dis,0x3f3f3f3f,sizeof(dis));
  dis[s]=0,vis[s]=true;
  q.push(s);
  while(!q.empty())
  {
    int p1=q.front();
    vis[p1]=false;
    q.pop();
    for(int i=0; i<G[p1].size(); i++)
    {
      int t=G[p1][i].to;
      dis[t]=min(dis[p1]+G[p1][i].val,dis[t]);
      if(!vis[t])
      {
        q.push(t);
        vis[t]=true;
      }
    }
  }
  for(int i=1; i<=n; i++)
    cout<<dis[i]<<" ";
  return 0;
}```