#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,s,a,b,c;
unsigned long long w[10009][10009];
unsigned long long dis[10009];
bool vis[10009];
const unsigned long long INF=2e31-1;
void dijkstra(int s)
{
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=0; 
	for(int i=1;i<=n;i++)
	{
		int u=-1;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&(u==-1||dis[j]<dis[u]))
			{
				u=j;
			} 
		}
		vis[u]=1;
		for(int j=1;j<=n;j++)
		{
			if(dis[j]>dis[u]+w[u][j]&&w[u][j]!=INF)
			{
				dis[j]=dis[u]+w[u][j];
			}
		}	
	}
	return ;
} 
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			w[i][j]=INF;
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		w[a][b]=min(w[a][b],c);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	cout<<endl;
	return 0;
}