#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
const long long INF =  2147483648; // 此处改成2^31-1 可以AC
int n,m,s;
int val[MAXN],nxt[MAXN],head[MAXN],to[MAXN];
long long dis[MAXN];
bool vis[MAXN];
int cnt = 0;
void add(int u,int v,int w)
{
	cnt++;
	val[cnt] = w;
	to[cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
}
void spfa()
{
	for(int i=1;i<=n;i++)
		dis[i] = INF;
	dis[0] =INF;
	dis[s] = 0;
	while(1)
	{
		int point = 0;
		for(int i=0;i<=n;i++)
			if(dis[i] < dis[point] && !vis[i]) point = i;
		if(point == 0) break;
		for(int i=head[point];i;i=nxt[i])
			if(dis[point] + val[i] < dis[to[i]]) dis[to[i]] = dis[point] + val[i];
		vis[point] = 1;
	}
}
int main()
{
	scanf("%d %d %d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++)
	{
		printf("%d ",dis[i]);
	}
	return 0;	
} 
/* 未通过测试点3
标准输入输出如下
in:
5 15 5
2 2 270
1 4 89
2 1 3
5 5 261
5 2 163
5 5 275
4 5 108
4 4 231
3 4 213
3 3 119
3 1 77
3 1 6
2 4 83
5 5 196
5 5 94


out:
166 163 2147483647 246 0 
*/