#include<bits/stdc++.h>
struct side
{
	int to, w;
};
struct node
{
	int u, w;
	bool operator <(node b) const
	{
		return w < b.w;
	}
};
int n, m, dis[100001], s;
std::vector<side> graph[100001];
bool vis[100001];
std::priority_queue<node> h;
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[u].push_back(side{v, w});
	}
	memset(dis,0x7f7f7f7f,sizeof(dis));
	dis[s] = 0;
	h.push(node{s, 0});
	while (!h.empty())
	{
		int x = h.top().u;
		h.pop();
		if(vis[x])continue;
		vis[x]=1;
		for (int i = 0; i < graph[x].size(); i++)
		{
			int y = graph[x][i].to,w=graph[x][i].w;
			if (dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				if(!vis[y])h.push(node{y, dis[y]});
			}
		}
	}
	for (int i = 1; i <= n; i++)printf("%d ", dis[i]);

}