#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt;
const int INF=INT_MAX;
struct node
{
	int v,w;
	friend bool operator <(node a,node b)
	{
		return a.w>b.w;
	}
}tmp;
int val[500010];
int dis[500010];
priority_queue<node>q;
int h[50010];
int to[500010],nxt[500010];
bool vis[500010];
void add(int a,int b,int c)
{
	to[++cnt]=b;
	val[cnt]=c;
	nxt[cnt]=h[a];
	h[a]=cnt;
}
inline int Dijkstra()
{
	for(int i=0;i<=n;i++)
	{
		dis[i]=INF;
	}
	dis[s]=0;
	tmp.v=s,tmp.w=0;
	q.push(tmp);
	while(!q.empty())
	{
		int u=q.top().v;
		q.pop();
		if(vis[u])
		{
			continue;
		}
		vis[u]=1;
		for(int i=h[u];i;i=nxt[i])
		{
			if(dis[to[i]]>(long long)dis[u]+val[i])
			{
				dis[to[i]]=dis[u]+val[i];
				tmp.w=dis[to[i]],tmp.v=to[i];q.push(tmp);
			}
		}
	}
}
int read()
{
	int p=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		p=p*10+(c-'0'),c=getchar();
	}
	return p;
}
void write(int l)
{
	if(l>=10)
	{
		write(l/10);
	}
	putchar(l%10+'0');
}
int main()
{
	n=read();
	m=read();
	s=read();
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		a=read();
		b=read();
		c=read();
		add(a,b,c);	
	}
	Dijkstra();
	for(int i=1;i<=n;i++)
	{
		write(dis[i]),putchar(' ');
	}
	return 0;
}

记录