#include<bits/stdc++.h>
using namespace std;

void dijkstra(vector<vector<pair<long long,long long>>>& graph,vector<long long>&dis,long long start)
{
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, less<pair<long long, long long>>> pq;
	dis[start] = 0;

	pq.push(make_pair(0, start));
	while (!pq.empty())
	{
		long long    u = pq.top().second;
		long long dist = pq.top().first;
		pq.pop();

		if (dist > dis[u]) continue;
		for (int i = 0; i < graph[u].size(); i++)
		{
			long long      v = graph[u][i].first;
			long long weight = graph[u][i].second;

			if (dis[u] != 1e9 && weight != 1e9 && dis[v] > dis[u] + weight) {
				dis[v] = dis[u] + weight;
				pq.push(make_pair(dis[v], v));
			}
		}
	}

}
int main()
{
	int n, m, s;
	cin >> n >> m >> s;

	vector<long long> dis(n + 1, 1e9);
	vector < vector<pair<long long, long long>>> graph(n + 1);
	for (int i = 1; i <= n; i++)
	{
		long long x, y, w;
		cin >> x >> y >> w;
		graph[x].push_back({ y,w });
	}

	dijkstra(graph,dis,s);

	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	return 0;
}