# include <iostream>
# include <vector>
# include <queue>
using namespace std;

struct node
{
	int x, key;
	bool operator < (const node & b)const{return key > b.key;}
};

const int N = 100005, inf = 2147483647;
vector<pair<int, int> > edge[N];
priority_queue<node> q;
int n, m, s, dis[N], vis[N];

void dijkstra(int s)
{
	for (int i = 1; i <= n; i++)
		dis[i] = inf;
	dis[1] = 0;
	q.push((node){s, dis[s]});
	while (q.size())
	{
		int u = q.top().x; q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int j = 0; j < edge[u].size(); j++)
		{
			int v = edge[u][j].first, w = edge[u][j].second;
			if (!vis[j] && dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				q.push((node){v, dis[v]});
			}
		}
	}
}

int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		edge[u].push_back(make_pair(v, w));
	}
	dijkstra(s);
	for (int i = 1; i <= n; i++)
		cout << dis[i] << ' ';
	cout << endl;
	return 0;
}