#include<cstdio>
#include<queue>

const int INF = 0x7fffffff;

struct Edge
{
	int to,dis,next;
};

int n, m, s;
int dis[10005], head[10005], cnt;

Edge e[500005];
bool vis[10005];
std::priority_queue< std::pair<int,int> > Q;

inline void add(int u, int v, int w)
{
	++cnt;
	e[cnt].to = v;
	e[cnt].dis = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

void dijkstra()
{
	for(register int i = 1; i <= n; ++i)
	{
		dis[i] = INF;
	}
	dis[s] = 0;
	
	Q.push(std::make_pair(0, s));
	while(!Q.empty())
	{
		int x = Q.top().second;
		Q.pop();
		if(vis[x])
		{
			continue;
		}
		vis[x] = true;
		for(register int i = head[x]; i != 0; i = e[i].next)
		{
			int y = e[i].to;
			if(dis[x] + e[i].dis < dis[y])
			{
				dis[y] = dis[x] + e[i].dis;
				Q.push(std::make_pair(dis[y], y));
			}
		}
	}
}

int main()
{
	std::scanf("%d %d %d", &n, &m, &s);
	for(register int i = 1; i <= m; ++i)
	{
		int u, v, w;
		std::scanf("%d %d %d", &u, &v, &w);
		add(u, v, w);
	}
	
	dijkstra();
	
	for(register int i = 1; i <= n; ++i)
	{
		std::printf("%d ", dis[i]);
	}
	
	return 0;
}