#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
int dist[N],st[N],g[N][N];
int n,m,s;
void dijkstra()
{
	memset(dist,0x3f,sizeof(dist)); 
	dist[s]=0;
	for(int i=1;i<=n;i++)
	{
		int u=-1;
		for(int j=1;j<=n;j++)
			if(!st[j] && (u==-1 || dist[u]>dist[j]))
				u=j;
		st[u]=1;
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[u]+g[u][j],dist[j]);
	}
}
int main()
{
	memset(g,0x3f,sizeof(g));
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int a,v,w;
		scanf("%d%d%d",&a,&v,&w);
		g[a][v]=w;
	}
	dijkstra();
	for(int i=1;i<=n;i++)
	{
		if(dist[i]==0x3f)
			printf("2147483647 ");
		else
			printf("%d ",dist[i]);
	}         
	return 0;     
}