#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define MX 100005
struct path{
	int now,dis;
	bool operator<(const path &another) const
	{
		return dis > another.dis;
	}
};
priority_queue <path> q;
vector <int> to[MX];
vector <int> cost[MX];
int n,m,s;
int dis[MX];
int vis[MX];
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);
		to[u].push_back(v);
		cost[u].push_back(w);
	}
	for (int i = 1;i <= n;i++)
	{
		dis[i] = 2147483647;
	}
	for (int i = 0;i < (int)to[s].size();i++)
	{
		dis[to[s][i]] = cost[s][i];
		q.push((path){to[s][i],dis[to[s][i]]});
	}
	dis[s] = 0;
	vis[s] = 1;
	while (!q.empty())
	{
		int now = q.top().now,d = q.top().dis;
		q.pop();
		if (vis[now] == 1)////有可能存在插队的情况 
		{
			continue;
		}
		vis[now] = 1;////比如 ： 更新为 8 进一次队列；更新为 5 进第二次队列;但 5 这次 先出队列，对外扩散后,之前的 8 已经没有意义了，来到时直接跳 
		for (int i = 0;i < (int)to[now].size();i++)
		{
			if (dis[to[now][i]] > d + cost[now][i])
			{
				dis[to[now][i]] = d + cost[now][i];
				q.push((path){to[now][i],dis[to[now][i]]});
			}
		}
	}
	for (int i = 1;i <= n;i++)
	{
		printf("%d ",dis[i]);
	}
	return 0;
}