#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#define INF 0x7FFFFFFF
using namespace std;
int cnt, n, m, s, head[10003], dis[10003];
struct EDGE
{
	int to, dis, next;
}edge[20000];
typedef pair<int, int> p;
priority_queue<p,vector<p>,greater<p> > q;
void add_edge()
{
	int from; cin >> from;
	cin >> edge[++cnt].to;
	cin >> edge[cnt].dis;
	edge[cnt].next = head[from];
	head[from] = cnt;
}
void init()
{
	cin >> n >> m >> s;
	for (int i = 0; i < m; ++i)
		add_edge();
	for (int i = 1; i <= n; ++i) dis[i] = INF;
}
void dijkstra()
{
	dis[s] = 0;
	q.push(p(0,s));
	while (!q.empty())
	{
		p node = q.top(); q.pop();
		int v = node.second;
		if (dis[v] < node.first)continue;
		for (int i = head[v]; i; i = edge[i].next)
		{
			if (dis[edge[i].to] > edge[i].dis + node.first)
			{
				dis[edge[i].to] = edge[i].dis + node.first;
				q.push(p(dis[edge[i].to], edge[i].to));
			}
		}
	}
}
void print()
{
	for (int i = 1; i <= n; ++i)
		cout << dis[i] << " ";
	printf("\b");
}
int main()
{
	init();
	dijkstra();
	print();
}