#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000003
#define maxm 1000003
using namespace std;
int n, m, s,k, head = 0, tail = 0, dis[maxn], u[maxm], v[maxm], w[maxm], first[maxn], gnext[maxm], que[maxn * 2], book[maxn];
int main()
{
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; ++i)
	{
		dis[i] = 99999999;
		book[i] = 0;
		first[i] = -1;
	}
	dis[s] = 0;
	//memset(first, -1, sizeof(first));
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d%d", &u[i], &v[i], &w[i]);
		gnext[i] = first[u[i]];
		first[u[i]] = i;
	}

	que[tail] = s; tail++;
	book[s] = 1;
	while (head<tail)
	{
		k = first[que[head]];
		while (k != -1)
		{
			if (dis[u[k]] + w[k] < dis[v[k]])
			{
				dis[v[k]] = dis[u[k]] + w[k];
				if (!book[v[k]])
				{
					book[v[k]]=1;
					que[tail] = v[k];
					++tail;
				}
			}
			k = gnext[k];
		}
		++head;
	}

	for (int i = 1; i <= n; ++i)
		printf("%d ", dis[i]);
	return 0;
}