#include <bits/stdc++.h>

using namespace std;

struct edge
{
	int u, v, w;
	edge(int a, int b, int c) : u(a), v(b), w(c) {}
};

vector<edge> e[100005];
int n, m, s, dis[100005], cnt[100005];
bool inque[100005];

bool SPFA(int start)
{
	queue<int> que;
	que.push(start);
	cnt[start] ++;
	dis[s] = 0;
	inque[s] = true;
	while (!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = false;
		for (int i = 0 ; i < e[u].size() ; i ++)
		{
			int v = e[u][i].v;
			int w = e[u][i].w;
			if (dis[u] + w < dis[v])
			{
				dis[v] = dis[u] + w;
				if (!inque[v])
				{
					inque[v] = true;
					que.push(v);
					cnt[v] ++;
					if (cnt[v] == n)
					{
						return false;
					}
				}
			}
		}
	}
	return true;
}

int main()
{
	memset(dis, 0x7f7f7f, sizeof(dis));
	cin >> n >> m >> s;
	for (int i = 1 ; i <= m ; i ++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back(edge(x, y, z));
	}
	if (SPFA(s))
	{
		for (int i = 1 ; i <= n ; i ++)
		{
			cout << dis[i] << " ";
		}
	}
	else
	{
		cout << ((1 << 31) - 1);
	}
	return 0;
}