#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5, MAXM=1e5+5;
int n, m, s;
struct Edge
{
	int u, v, w, nxt;
}edge[MAXM];
int cnt, head[MAXN];
struct node
{
	int a, b;
	bool operator <(const node &x) const
	{
		return x.a<a;
	}
};

priority_queue<node> q;

void add(int u, int v, int w)
{
	edge[++cnt]={u, v, w, head[u]};
	head[u]=cnt;
}

int dis[MAXN];
bool check[MAXN];

int main()
{
	memset(dis, 0x3f, sizeof(dis));
	cin>>n>>m>>s;
	for(int i=1; i<=m; i++)
	{
		int u, v, w;
		cin>>u>>v>>w;
		add(u, v, w);
	}
	dis[s]=0;
	q.push({0, s});
	while(q.size())
	{
		node k=q.top();
		q.pop();
		int b=k.b;
		if(check[b]) continue;
		check[b]=1;
		for(int i=head[b]; i; i=edge[i].nxt)
		{
			int v=edge[i].v, w=edge[i].w;
			if(dis[v]>dis[b]+w)
			{
				dis[v]=dis[b]+w;
				if(!check[v])
					q.push({dis[v], v});
			}
		}
	}
	for(int i=1; i<=n; i++)
	{
		cout<<dis[i]<<" ";
	}
	
}