#include <bits/stdc++.h>
#define inf 0x7f7f7f7f
using namespace std;
class Edge
{
public:
	int l,r,nextline;
	long long val;
}eline[4000000];
class Number
{
public:
	int n;
	long long v;
};
priority_queue<Number> won;
bool visited[800000];
int elast[800000],n,m;
long long dis[800000];
bool operator<(Number L,Number R)
{
	return L.v>R.v;
}
int main()
{
	//最短路默写2
	int s,i,j;
	scanf("%d%d%d",&n,&m,&s);
	for(i=1;i<=n;i++) dis[i]=inf;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%lld",&eline[i].l,&eline[i].r,&eline[i].val);
		eline[i].nextline=elast[eline[i].l];
		elast[eline[i].l]=i;
	}
	dis[s]=0;
	Number _now;
	_now.v=0,_now.n=s;
	won.push(_now);
	while(!won.empty())
	{
		_now=won.top();
		won.pop();
		if (visited[_now.n]) continue;
		if (_now.n==n) break;
		visited[_now.n]=true;
		for(i=elast[_now.n];i!=0;i=eline[i].nextline)
			if (dis[eline[i].r]>dis[_now.n]+eline[i].val)
			{
				dis[eline[i].r]=dis[_now.n]+eline[i].val;
				Number temp;
				temp.v=dis[eline[i].r];
				temp.n=eline[i].r;
				won.push(temp);
			}
	}
	for(i=1;i<=n;i++) printf("%lld ",dis[i]);
}