QwQ

#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt;
long long d[100010];
struct node
{
	int go,next;
	long long w;
}a[400020];
struct node2
{
	int v;
	long long dv;
	bool operator<(const node2& other)const
	{
		dv>other.dv;
	}
};
int head[100010];
bool lo[100010];
void add(int x,int y,int w)
{
	cnt++;
	a[cnt].go=y;
	a[cnt].next=head[x];
	a[cnt].w=w;
	head[x]=cnt;
}
void dij()
{
	priority_queue<node2> q;
	for (int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
	d[s]=0;
	q.push({s,0});
	while (!q.empty())
	{
		node2 b=q.top();
		q.pop();
		int u=b.v;
		if (lo[u]) continue;
		lo[u]=1;
		for (int j=head[u];j;j=a[j].next)
		{
			int go=a[j].go;
			if (d[go]>=d[u]+a[j].w)
			{
				d[go]=d[u]+a[j].w;
				q.push({go,d[go]});
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for (int i=1;i<=m;i++)
	{
		int u,v;
		long long w;
		cin>>u>>v>>w;
		add(u,v,w);
//		add(v,u,w);
	}
	dij();
	for (int i=1;i<=n;i++) cout<<d[i]<<" ";
	return 0;
}