int n,m,k;
int dis[10005];
int vis[10005];
int head[500005];
int num=0;
struct edge{
	int next;
	int to;
	int val;
}edge[500005];
void addedge(int from,int to,int val)
{
	edge[++num].next=head[from];
	edge[num].to=to;
	edge[num].val=val;
	head[from]=num;
}
void spfa()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		dis[i]=0x3f3f3f;
		vis[i]=0;
	}
	q.push(k);
	dis[k]=0;//权值 
	vis[k]=1;//标记入队
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].val)
			{
				dis[v]=dis[u]+edge[i].val;
				if(vis[v]==0)
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	 } 
}
void solve() {
	std::ios::sync_with_stdio(0);
	std::cin.tie();
	std::cout.tie();
   cin>>n>>m>>k;
   while(m--)
   {
   	int a,b,c;
   	cin>>a>>b>>c;
   	addedge(a,b,c);
   }
   spfa();
   for(int i=1;i<=n;i++)
   {
   	if(i==k)
   	cout<<0<<" ";
   	else
     cout<<dis[i]<<" ";
 }
    return ;
}
int main() {
	solve();
	return 0;
}