#include<iostream>
using namespace std;
typedef long long ll;
ll e[10001][10001], dis[50005], book[50005], t1, t2, t3;
ll y;
int main()
{
	ll n, m, s;
	ll inf = 2147483647;
	cin >> n >> m >> s;

	for (int i = 1; i <= n; i++)
		book[i] = 0;
	book[s] = 1;

	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = inf;
		}

	for (int i = 1; i <= m; i++)
	{
		cin >> t1 >> t2 >> t3;
		e[t1][t2] = t3;
	}

	for (int i = 1; i <= n; i++)
		dis[i] = e[s][i];

	for (int i = 1; i <= n - 1; i++)
	{
		ll min = inf;
		for (int j = 1; j <= n; j++)
		{
			if (book[j] == 0 && dis[j] < min)
			{
				min = dis[j];
				y = j;
			}
		}

		book[y] = 1;
		for (int i = 1; i <= n; i++)
		{
			if (e[y][i] < inf)
			{
				if (dis[i] > dis[y] + e[y][i])
					dis[i] = dis[y] + e[y][i];
			}
		}
	}
	for (int i = 1; i < n; i++)
		cout << dis[i] << ' ';
	cout << dis[n];
	return 0;