#include <cstdio>
#include <queue>
#define maxn 100003
#define maxm 1000003
struct Edge
{
	int next;
	int to;
	int dis;
};
std::queue<int> que;
int n, m, s,num_edge=0, dis[maxn], book[maxn],first[maxn];
struct Edge edge[maxm];

void addedge()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	edge[++num_edge].next = first[a];
	edge[num_edge].to = b;
	edge[num_edge].dis = c;
	first[a] = num_edge;
	return;
}

void SPFA()
{
	while (!que.empty())
	{
		int k = que.front();
		que.pop(); book[k] = 0;
		for (int i = first[k]; i; i = edge[i].next)
		{
			if (dis[edge[i].to] > dis[k] + edge[i].dis)
			{
				dis[edge[i].to] = dis[k] + edge[i].dis;
				if (!book[edge[i].to])
				{
					book[edge[i].to] = 1;
					que.push(edge[i].to);
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; ++i)
		addedge();
	for (int i = 1; i <= n; ++i)
		dis[i] = 99999999;
	que.push(s);
	dis[s] = 0;
	book[s] = 1;
	SPFA();
	
	for (int i = 1; i <= n; ++i)
		printf("%d ", dis[i]);
	return 0;
}