#include<iostream>
#include<queue>
using namespace std; 
struct Dis
{
	int to;
	int w;
};
struct DisCompingFunction
{
	bool operator()(Dis DisCompFrom,Dis DisComp)
	{
		return DisCompFrom.w>DisComp.w;
	}
};
struct Road
{
	int length;
	int to;
	Road *NextRoad;
};
Road *From[10001],Line[500001];
Dis dis[10001];
int alla=0,n,m;
bool flag[10001];
void add(int a,int b,int v)
{
	alla++;
	Line[alla].length=v;
	Line[alla].to=b;
	Line[alla].NextRoad=From[a];
	From[a]=&Line[alla];
}
int Input()
{
	int s;
	cin>>n>>m>>s;
	int a,b,v;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>v;
		add(a,b,v);
	}
	return s;
}
priority_queue<Dis,vector<Dis>,DisCompingFunction>He;
int Dijkstra(int begin)
{
	for(int i=1;i<=n;i++)
	{
		dis[i].to=i;
		dis[i].w=2147483647;
	}
	dis[begin].w=0;
	He.push(dis[begin]);
	int x;
	flag[0]=true;
	while(!He.empty())
	{
		x=He.top().to;
		  He.pop();
		  if(flag[x])continue;
		flag[x]=true;
		for(Road *i=From[x];i;i=i->NextRoad)
		{
			int j=i->to,k=i->length;
			if(flag[j]==false&&dis[x].w+k<dis[j].w)
			{
				dis[j].w=dis[x].w+k;
				He.push(dis[j]);
			}
		}
	}
}
int main()
{
	Dijkstra(Input());
	for(int i=1;i<=n;i++)
	{
		//if(dis[i].w>=99999999)cout<<2147483647<<endl;
		cout<<dis[i].w<<" ";
	}
}