#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
int n, m, s, cnt = 0;
struct node
{
	int w, to, nxt;
}e[500001];
struct edge
{
	int v, w;
	friend bool operator<(node a, node b)
	{
		return a.w > b.w;
	}
};
priority_queue<edge> q;
int h[10001], dis[10001];
bool vis[500001];
inline void add(int u, int v, int w) //链式前向星 
{
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = h[u];
	h[u] = cnt;
}
inline void dijkstra()
{
	for(int i = 0; i <= n; i++)
		dis[i] = INF;
	dis[s] = 0;
	q.push((edge){s, 0});
	while(!q.empty())
	{
		int u = q.top().v; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = h[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].w)
			{
				dis[v] = dis[u] + e[i].w;
				q.push((edge){v, dis[v]});
			}
		}
	}
}
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void write(int x)
{
	if(x < 0)
	{
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
int main()
{
	n = read(), m = read(), s = read();
	for(int i = 1; i <= m; i++)
	{
		int u = read(), v = read(), w = read();
		add(u, v, w);
	}
	dijkstra();
	for(int i = 1; i <= n; i++)
	{
		write(dis[i]);
		putchar(' ');
	}
	return 0;
}