typedef pair<int,int> PII;
const int N=500005;
int n;
int  h[N],w[N],e[N],ne[N],idx;//邻接表  
int dist[N];//距离 
bool st[N];//检测是否包含 
void add(int a,int b,int c)
{
	e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void dijkstra(int id)//跑一次可以知道从指定点到其他所有点的最短路距离,不用重复跑， 
{
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);
	dist[id]=0;
	priority_queue<PII,vector<PII>,greater<PII> >heap;
	heap.push({0,id});//first存距离 second存节点编号 
	while(!heap.empty())
	{
		PII t=heap.top();
		heap.pop();
		int ver = t.second,distance = t.first;
		if(st[ver]) continue;//存在就不要了
		for(int i=h[ver];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>distance+w[i])
			{
				dist[j]=distance+w[i];
				heap.push({dist[j],j});
			}
		 } 
	}
	for(int i=1;i<=n;i++) 
		if(i==id) cout<<0<<" ";
		else 
		{
			if(dist[i]==0x3f3f3f3f)cout<<pow(2,31)-1<<" ";
			else cout<<dist[i]<<" "; 
		}
}
int main()
{
	int m,start;
	cin>>n>>m>>start;
	idx=0;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=m;i++) 
	{
		int a,b,val;
		cin>>a>>b>>val;
		add(a,b,val);
	}
	dijkstra(start);
	return 0;
}
  //头文件已经设置了，90分求助，看不出来（捂脸