RT

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define mem(x,val) memset((x),(val),(sizeof(x)))
using namespace std;
const int INF = 0x7fffffff;
const int S = 5*1e5+5;
int n,m,s,tot;
LL head[S],ver[S],edge[S],Next[S],dis[S],vis[S];
queue <LL> q;
inline void add(int x,int y,int z)
{ver[++tot] = y,edge[tot] = z,Next[tot] = head[x],head[x] = tot;}
inline void spfA()
{
	mem(dis,0x7f);	
	dis[s] = 0; 
	vis[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for(int i = head[x];i;i = Next[i])
		{
			int y = ver[i],z = edge[i];
			if(dis[y] > dis[x]+z)
			{
				dis[y] = dis[x]+z;
				if(!vis[y]) {q.push(y);vis[y] = 1;}
			}
		}
	}
}
inline LL read()
{
	LL x=0,f=1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return f*x;
}
int main(int argc,char *argv[])
{ 
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);	
	n = read(),m = read(),s = read();
	for(int i = 1;i <= m;++i)
	{
		int u = read(),v = read(),w = read();
		add(u,v,w);
	}
	spfA();
	for(int i = 1;i <= n;++i) 
	{
		if(s == i) {printf("0 ");continue;}
		printf("%lld ",dis[i]);
	}
	//printf("Tide used = %.0lf.ds\n",((double)clock()/(double)CLOCKS_PER_SEC) * 1000.0);
	return 0;
}