#include<bits/stdc++.h>
using namespace std;
struct bian{
	int to,w;
};
vector<bian>maps[500005];
int dis[500005];
int book[500005]={0};
int n,m,s;

int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		dis[i]=1919810;
	}
		dis[s]=0;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		if(u==s) 	dis[v]=w;
		maps[u].push_back(bian{v,w});
	}
	for(int i=1;i<=n-1;i++)
	{
		int gg;
		int b;
		int min=1919810;
		for(int j=1;j<=n;j++)
		{
			if(book[j]==0&&dis[j]<min)
			{
				min=dis[j];
				b=j;
			}
			book[j]=1;
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=maps[b].size();k++)
				{
					if(maps[b][k].to==j)	gg=k;
				}
				if(dis[j]>dis[b]+maps[b][gg].w)
				{
					dis[j]=dis[b]+maps[b][gg].w;
				}
			}
			
		}
		
		
		
	}
	
	
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<' ';
	}
	
	
	
	
	
	
	
	return 0;
}