#include<bits/stdc++.h>
#define inf 1000000001

struct side
{
	int to;
	int w;
	bool operator <(side b) const
	{
		return w < b.w;
	}
};
struct path
{
	int u,v;
	bool operator<(path b)const
	{
		return u+v<b.u+b.v;
	}
};
int n, m, s;
int dis[100001];
std::priority_queue<side> h;
std::map<path,int> graph;
int main()
{
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		graph[path{u,v}] = w;
	}
	for (int i = 1; i <= n; i++)
		dis[i] = inf;
	
	dis[s] = 0;
	h.push(side{s, 0});
	while (!h.empty())
	{
		side tmp = h.top();
		h.pop();
		int x = tmp.to;
		if (dis[x] != tmp.w)continue;
		for (int i = 1; i <= n; i++)
		{
			if (graph.count(path{x,i})==0)continue;
			
			int y = i, w =graph[path{x,i}];
			if (dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				h.push(side{y, dis[y]});
			}
		}
	}
	for (int i = 1; i <= n; i++)printf("%d ", dis[i]);
	
}