#include<iostream>
#include<cstring>
#include<algorithm>
#define mm 20000001
#define inf 0x7f
using namespace std;
int n,m,s,cnt;
int h[2000001],dis[mm];
bool visit[mm];
struct Edge{
	int to,w,next;
}edge[2000001];
void init ()
{
	memset(visit,0,sizeof(visit));
	memset(dis,inf,sizeof(dis));
	memset(h,-1,sizeof(h));
}
void add(int u,int v,int w)
{
	edge[cnt].to=v,edge[cnt].w=w,edge[cnt].next=h[u],h[u]=cnt++;
}
void pintf()
{
	for(int i=1;i<=n;i++)
	{
		/*if(dis[i]==0x7f)
		cout<<"2147483647";
		else */
		cout<<dis[i]<<' ';
	}
}
void Dijkstra()
{
	int minn,pos;
	while(1)
	{
		minn=inf,pos=-1;
		for(int i=1;i<=n;i++)
		{
			if(!visit[i]&&dis[i]<minn)
			{
				minn=dis[i],pos=i;
			}
		}
		if(pos==-1)break;
		visit[pos]=1;
		for(int i=h[pos];i!=-1;i=edge[i].next)
		{
			int t=edge[i].to;
			if(!visit[t]&&dis[t]>dis[pos]+edge[i].w)
			dis[t]=dis[pos]+edge[i].w;
		}
	}
	return ;
}
int main ()
{
	cin>>n>>m>>s;
	init();
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dis[s]=0;
	Dijkstra();
	pintf();
	return 0;
}