#include <bits/stdc++.h>
using namespace std;
struct edge{
	int to,nxt,w;
};
//链式前向星 
edge martix[500020];
int head[114514];
int dist[114514];
bool flag[114514];
int main()
{
	memset(head,-1,sizeof(head));
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	memset(dist,2147483647,sizeof(dist)); 
	dist[s]=0;
	flag[s]=1;
	for(int i = 1;i <= m;i++)
	{
		int t;
		scanf("%d%d%d",&t,&martix[i].to,&martix[i].w);
		martix[i].nxt=head[t];
		head[t]=i;
		if(t==s)
			dist[martix[i].to]=martix[i].w;
	}
	//dijkstra开始微操
	for(int i = 1;i <= n;i++)
	{
		int min = 0x3f3f,index;
		for(int j = 1;j <= n;j++)
		{
			if(dist[j]<min&&flag[j]==0)
			{
				min = dist[j];
				index=j;
			}
		}
		flag[index]=1;
		for(int j = head[index];j != -1;j = martix[j].nxt)
		{
			if(dist[index]+martix[j].w<dist[martix[j].to]&&flag[martix[j].to]==0)
				dist[martix[j].to]=dist[index]+martix[j].w;
		}
	}
	for(int i = 1;i <= n;i++)
		printf("%d ",dist[i]);
	return 0;
}

华丽丽的手残了