#include <bits/stdc++.h>
using namespace std;
int n,m,tot,s;
int ver[1000000],edge[1000000],Next[1000000],head[1000000];
int d[1000000];
bool v[1000000];
queue<int> q;
void add(int x, int y, int z)
{
   ver[++tot]=y;
   edge[tot]=z;
   Next[tot]=head[x];
   head[x]=tot;
}
void spfa()
{
   memset(d,0x3f,sizeof(d));
   memset(v,0,sizeof(v));
   d[s]=0;
   v[s]=1;
   q.push(s);
   while(q.size())
   {
      int x=q.front(); q.pop();
      v[x]=0;
      for (int i=head[x]; i; i=Next[i])
      {
	     int y=ver[i];
	     int z=edge[i];
	     if (d[y]>d[x]+z)
	     {
		    d[y]=d[x]+z;
		    if (!v[y]) q.push(y),v[y]=1;
		 }
	  }
   }
}
int main()
{
   cin>>n>>m>>s;
   for (int i=1; i<=m; i++)
   {
      int x,y,z;
      cin>>x>>y>>z;
      add(x,y,z);
   }
   spfa();
   for (int i=1; i<=n; i++)
   {
      cout<<d[i]<<endl;
   }
   return 0;
}