#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int nod,nr,nh,r,z,x,y,i,j,k,n,m,c[2000][2000],p[2000],d[2000],h[2000],poz[2000];
void drum(int i)
{if(i==r)
	{
g<<i<<" ";}
else
{drum(p[i]);
g<<i<< " ";
}
}


void up(int k)
{int t,aux;
while(t>0)
{t=k/2;
if(d[h[t]]>d[h[k]])
{aux=h[t];
h[t]=h[k];
h[k]=aux;
poz[h[t]]=t;
poz[h[k]]=k;
k=t;
}
else
	t=0;
}
}
void down(int r,int k)
{int t,i,aux;
t=r;i=2*t;
while(i<=k)
{if((i+1<=k)&&(d[h[i]]<d[h[i+1]]))
	i=i+1;
if(d[h[t]]>d[h[i]])
{aux=h[t];
h[t]=h[i];
h[i]=aux;
poz[h[t]]=t;
poz[h[i]]=i;
i=t;
}
else
	i=k+1;}
}
int main()
{f>>n>>m>>r;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		if(i!=j)
		c[i][j]=30000;
	for(i=1;i<=m;i++)
	{f>>x>>y>>z;
	c[x][y]=c[y][x]=z;
	
	}
	for(i=1;i<=n;i++)
	{d[i]=c[r][i];
	if(d[i]<32000)
		p[i]=r;
		}

	p[r]=0;
	for(i=1;i<=n;i++)
	{h[i]=i;
	poz[i]=i;
	}
	for(i=1;i<=n;i++)
		up(i);
nh=n;
while(nh)
{
h[1]=h[nh];
poz[h[1]]=1;
nh--;
down(1,nh);
nod=h[1];
for(i=1;i<=n;i++)
	if(d[nod]+c[nod][i]<d[i])
	{d[i]=d[nod]+c[nod][i];
	p[i]=nod;
	up(poz[i]);
	}
}
for(i=1;i<=n;i++)
			if(i!=r&&d[i]<32000)
				g<<d[i]<<" ";
			else
				g<<0<<" ";


f.close();
g.close();
return 0;
}